The number of rooted forests in circulant graphs

Abstract

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,\dots ,s_k)$ and $G=C_{2n}(s_1,s_2,\dots ,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)=pa(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 _{i=1}^k(z^{s_i}+z^{-s_i}).$

14 pages. arXiv admin note: substantial text overlap with arXiv:1711.00175, arXiv:1812.04484