  In this paper, we investigate characteristic polynomials of matrices in
min-plus algebra. Eigenvalues of min-plus matrices are known to be the minimum
roots of the characteristic polynomials based on tropical determinants which
are designed from emulating standard determinants. Moreover, minimum roots of
characteristic polynomials have a close relationship to graphs associated with
min-plus matrices consisting of vertices and directed edges with weights. The
literature has yet to focus on the other roots of min-plus characteristic
polynomials. Thus, here we consider how to relate the 2nd, 3rd,... minimum
roots of min-plus characteristic polynomials to graphical features. We then
define new characteristic polynomials of min-plus matrices by considering an
analogue of the Faddeev-LeVerrier algorithm that generates the characteristic
polynomials of linear matrices. We conclusively show that minimum roots of the
proposed characteristic polynomials coincide with min-plus eigenvalues, and
observe the other roots as in the study of the already known characteristic
polynomials. We also give an example to illustrate the difference between the
already known and proposed characteristic polynomials.
