Speaker
Description
The purpose of this report is to study the spectral invariants of circulant graphs and their generalizations. Circulant graphs arise as cyclic coverings of a single-vertex graph with a given number of loops. More complex representatives of the family of cyclic coverings are I-, Y-, H-graphs, generalized Petersen graphs, sandwich graphs, discrete tori, and many others.
In the talk, analytical formulas will be given that allow one to calculate the number of rooted spanning forests and trees in cyclic coverings, their asymptotics will be found, and the arithmetic properties of these numbers will be studied. In addition, for circulant graphs, exact formulas for calculating the Kirchhoff index will be indicated and it will be established that, up to an exponentially small remainder term, they are given by polynomials of the third degree.
All these quantities are spectral invariants. They depend on the eigenvalues of the characteristic polynomial of the Laplace matrix. The structure of the polynomial itself for circulant graphs remained unknown. In recent papers [Xiaogang Liu and Sanming Zhou (2012), Xiaogang Liu and Pengli Lu (2016)], it was found that the characteristic polynomials for a number of well-known families of graphs, such as the theta graph, dumbbell graph, and propeller graph, are effectively expressed in terms of Chebyshev polynomials. These results gave the key to understanding the structure of the characteristic polynomial for circulant graphs.
We will show that the characteristic polynomial can be represented as a finite product of algebraic functions calculated in the roots of a linear combination of Chebyshev polynomials. In particular, this will make it possible to establish the periodicity of such polynomials at prescribed integer points, which is of interest from the point of view of discrete topological dynamics.
References
[1] A.D. Mednykh, I.A. Mednykh, Cyclic coverings of graphs. Enumeration of rooted spanning forests and trees, Kirchhoff index and Jacobians. Uspehi matematiheskikh nauk, 2023, Vol. 78, Is. 3(471), p. 115-160.
