The number of rooted forests in circulant graphs

Lilya A. Grunwald, Ilya Mednykh


In 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) = pa(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+zsi).


rooted tree, spanning forest, circulant graph, Laplacian matrix, Chebyshev polynomial, Mahler measure

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications