The number of rooted forests in circulant graphs - Grunwald, Lilya A. (Ars mathematica contemporanea, 2022)
In this paper, we develop a new method to produce explicit formulas for the number ?$f_{G}(n)$? of rooted spanning forests in the circulant graphs ?$G=C_{n}(s_1,s_2,…,s_k)$? and ?$ G=C_{2n}(s_1,s_2,…,s_k,n)$?. These formulas are expressed through Chebyshev polynomials. We prove that in both cases the number of rooted spanning forests can be represented in the form ?$f_{G}(n)=p\,a(n)^2$?, where ?$a(n)$? is an integer sequence and ?$p$? is a prescribed natural number depending on the parity of ?$n$?. Finally, we find an asymptotic formula for ?$f_{G}(n)$? through the Mahler measure of the associated Laurent polynomial ?$P(z) = 2k+1-\sum\limits_{i = 1}^k(z^{s_i}+z^{-s_i})$?.
Keywords: Chebyshev polynomial; circulant graph; krožni graf; Laplaceova matrika; Laplacian matrix; Mahler measure; Mahlerjeva mera; polinom Čebiševa; rooted tree; spanning forest; vkoreninjeno drevo; vpeti gozd