The structure of the characteristic polynomial of Laplace matrix for circulant graphs with non-fixed jumps

The main objects of the present paper are circulant graphs with non-fixed jumps. The paper describes the structure of characteristic polynomial $\chi_{\mathscr L}(\mu)$ of Laplace matrix of such a graphs. It is shown that characteristic polynomial can be presented as a product of algebraic functions, each of them is expressed through the roots of linear combination of Chebyshrev polynomials of the first kind. Also, it is proved that $\chi_{\mathscr L}(\mu)$ is always a square of an integer polynomial, multiplied by some prescribed integer polynomial. As an example of application, the formula for the number of rooted spanning forests in such a graphs is given.

УДК 517.535+519.177

Keywords: circulant graph, rooted spanning forest, characteristic polynomial, Laplace matrix.