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₁,s₂,…,s_k) and G = C_2n(s₁,s₂,…,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)², where a(n) is an integer sequence and p is a certain 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−∑_i = 1^k(z^s_i+z^−s_i).