Abstract: We study the complexity of an infinite family of graphs Hn=Hn (G1,G2,...,Gm) that are discrete Seifert foliations over a given graph H on m vertices with fibers G1,G2,...,Gm. Each fiber Gi = Cn(Si,1,Si,2,...,Si,ki) of this foliation is a circulant graph on n vertices with jumps Si,1,Si,2,...,Si,ki. 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 τ(n) of spanning trees in Hn is obtained in terms of Chebyshev polynomials, some analytical and arithmetic properties of this function are investigated, and its asymptotics as n → ∞ is determined.