COUNTING ROOTED SPANNING FORESTS FOR CIRCULANT FOLIATION OVER A GRAPH

摘要

In this paper, we present a new method to produce explicit formu-las for the number of rooted spanning forests f (n) for the infinite family of graphs Hn = Hn (G1, G2, . . . , Gm) obtained as a circulant foliation over a graph H on m ver-tices 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 . This family includes the family of generalized Petersen graphs, I-graphs, sandwiches of circulant graphs, discrete torus graphs and others.The formulas are expressed through Chebyshev polynomials. We prove that the number of rooted spanning forests can be represented in the form f (n) = p f (H)a(n)2, where a(n) is an integer sequence and p is a prescribed natural number depending on the number of odd elements in the set of si, j. Finally, we find an asymptotic formula for f (n) through the Mahler measure of the associated Laurent polynomial.