Complexity of Discrete Seifert Foliations over a Graph

Abstract

We study the complexity of an infinite family of graphs \({{H}_{n}} = {{H}_{n}}({{G}_{1}},{{G}_{2}}, \ldots ,{{G}_{m}})\) that are discrete Seifert foliations over a given graph H on m vertices with fibers \({{G}_{1}},{{G}_{2}}, \ldots ,{{G}_{m}}.\) Each fiber G_i = \({{C}_{n}}({{s}_{{i,1}}},{{s}_{{i,2}}},...,{{s}_{{i,{{k}_{i}}}}})\) of this foliation is a circulant graph on n vertices with jumps \({{s}_{{i,1}}},{{s}_{{i,2}}}, \ldots ,{{s}_{{i,{{k}_{i}}}}}.\) The family of discrete Seifert foliations is sufficiently large. It includes the generalized Petersen graphs, I-graphs, Y-graphs, H-graphs, sandwiches of circulant graphs, discrete torus graphs, and other graphs. A closed-form formula for the number \(\tau (n)\) of spanning trees in H_n is obtained in terms of Chebyshev polynomials, some analytical and arithmetic properties of this function are investigated, and its asymptotics as \(n \to \infty \) is determined.