The number of rooted forests in circulant graphs
Keywords:rooted tree, spanning forest, circulant graph, Laplacian matrix, Chebyshev polynomial, Mahler measure
AbstractIn this paper, we develop a new method to produce explicit formulas for the number fG(n) of rooted spanning forests in the circulant graphs G = Cn(s1,s2,…,sk) and G = C2n(s1,s2,…,sk,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 fG(n) = p a(n)2, 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 fG(n) through the Mahler measure of the associated Laurent polynomial P(z) = 2k + 1−∑i = 1k(zsi+z−si).
Articles in this journal are published under Creative Commons Attribution 4.0 International License