In the present paper, we study the complexity of an infinite family of graphs Hn = Hn(G1, G2, ..., Gm) that are discrete Seifert foliations 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. 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 graph and others. We obtain a closed formula for the number t(n) of spanning trees in Hn in terms of Chebyshev polynomials, investigate some arithmetical properties of this function and find its asymptotics as n → ∞.
В настоящей работе мы рассматриваем бесконечное семейство графов Hn = Hn(G1, G2, ..., Gm), представляющих из себя дискретные расслоения Зейферта над заданным графом H на m вершинах с особыми слоями G1, G2, ..., Gm. Каждый слой Gi = Cn(si,1, si,2, ..., si,ki) такого расслоения является циркулянтным графом на n вершинах со скачками si,1, si,2, ..., si,ki. Семей-ство дискретных расслоений Зейферта достаточно обширно. Оно включает обобщённые графы Петерсена, I-графы, Y-графы, H-графы, сандвичи циркулянтных графов, дискретные торы и др. В работе получены формулы для числа порождающих деревьев t(n) графа Hn в терминах полиномов Чебышева, изучены аналитические и арифметические свойства этой функции и найдена её асимптотика при n → ∞.