In the present paper, we investigate the complexity of 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, I-graphs, sandwiches of circulant graphs, discrete torus graphs and others. We obtain a closed formula for the number τ(n) of spanning trees in Hn in terms of Chebyshev polynomials, investigate some arithmetical properties of this function and find its asymptotics as n→ ∞.
Предметные области OECD FOS+WOS
- 1.01 МАТЕМАТИКА