Tohoku Math. J.
74 (2022), 535-548
|
Title
COUNTING ROOTED SPANNING FORESTS FOR CIRCULANT FOLIATION OVER A GRAPH
Author
Liliya A. Grunwald, Young Soo Kwon and Ilya Mednykh
(Received June 7, 2021, revised August 6, 2021) |
Abstract.
In this paper, we present a new method to produce explicit formulas for the number of rooted spanning forests $f(n)$ for the infinite family of graphs $H_n=H_n(G_1,G_2,\ldots,G_m)$ obtained as a circulant foliation over a 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},\ldots,s_{i,k_i})$ of this foliation is the circulant graph on $n$ vertices with jumps $s_{i,1},s_{i,2},\ldots,s_{i,k_i}.$ 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 $s_{i,j}.$ Finally, we find an asymptotic formula for $f(n)$ through the Mahler measure of the associated Laurent polynomial.
Mathematics Subject Classification.
Primary 05C30; Secondary 39A10.
Key words and phrases.
Spanning forest, rooted forest, circulant graph, $I$-graph, $Y$-graph, $H$-graph, Laplacian matrix, Chebyshev polynomial.
|
|
