Complexity of the circulant foliation over a graph

2019/02/15 by Kwon, Young Soo, Mednykh, Alexander, Mednykh, Ilya · 1 citation
#05C30 #39A10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1902.05681

Abstract

In the present paper, we investigate the complexity of infinite family of graphs H_n=H_n(G₁, G₂,…,G_m) obtained as a circulant foliation over a graph H on m vertices with fibers G₁, G₂,…,G_m. Each fiber G_i=C_n(s_i,1, s_i,2,…,s_i,k_i) of this foliation is the circulant graph on n vertices with jumps s_i,1, s_i,2,…,s_i,k_i. 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 H_n in terms of Chebyshev polynomials, investigate some arithmetical properties of this function and find its asymptotics as n→∞.

Cited by

• The number of rooted spanning forests of bicirculant graphs

Related

• On the structure of Laplace characteristic polynomial for circulant foliation
• Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics
• The number of spanning trees in circulant graphs, its arithmetic\n properties and asymptotic
• The number of rooted forests in circulant graphs
• On the complexity of Cayley graphs on a dihedral group