Abstract: In this paper, we describe the structure of the Laplacian characteristic polynomial χn(λ) for the infinite family of graphs Hn = Hn(G1, G2,...,Gm) obtained as a circulant foliation over a graph H on m vertices with fibers G1, G2,...,Gm. Each fiber Gi = Cn(si,1, si,2, . . . , si,ki ) of this foliation is the circulant graph on n vertices with jumps si,1, si,2, . . . , si,ki . This family includes the family of generalized Petersen graphs, Igraphs, sandwiches of circulant graphs, discrete torus graphs and others. We show that the characteristic polynomial for such graphs can be decomposed into a finite product of algebraic functions evaluated at the roots of a linear combination of Chebyshev polynomials. Also, we prove that the characteristic polynomial can be represented in the form χn(λ) = p(λ)χH(λ)a(n)2, where a(n) is a sequence of integer polynomials and p(λ) is a prescribed integer polynomial depending on the number of odd elements in the set of si,j. Moreover, we use the obtained results to produce analytic formulas for spectral graph invariants, such as the number of spanning trees and the number of spanning rooted forests.

Cite: Kwon Y.S. , Mednykh A.D. , Mednykh I.A.
On the structure of Laplacian characteristic polynomial for circulant foliation
Discrete Applied Mathematics. 2025. V.375. P.338-349. DOI: 10.1016/j.dam.2025.06.046 Scopus

Dates:

Submitted:	Feb 2, 2025
Accepted:	Jun 22, 2025
Published online:	Jul 7, 2025
Published print:	Oct 15, 2025

Identifiers:

Scopus:

2-s2.0-105009414495

Citing: Пока нет цитирований

Altmetrics: