Complexity of the circulant foliation over a graph

Abstract

In the present paper, we investigate the complexity of infinite family of graphs $H_n=H_n(G_1,G_2,\dots ,G_m)$ obtained as a circulant foliation over a graph $H$ on $m$ vertices with fibers $G_1,G_2,\dots ,G_m.$ Each fiber $G_i=C_n(s_{i,1},s_{i,2},\dots ,s_{i,k_i})$ of this foliation is the circulant graph on $n$ vertices with jumps $s_{i,1},s_{i,2},\dots ,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 $\tau (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\to \infty .$

14 pages