ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P4.10 / 675–686
https://doi.org/10.26493/1855-3974.2029.01d
(Also available at http://amc-journal.eu)
The number of rooted forests in circulant
graphs*
Lilya A. Grunwald , Ilya Mednykh †
Sobolev Institute of Mathematics, 630090, Novosibirsk, Russia
Novosibirsk State University, 630090, Novosibirsk, Russia
Received 28 June 2019, accepted 28 February 2022, published online 26 August 2022
Abstract
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) = 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−
∑k
i=1(z
si+z−si).
Keywords: Rooted tree, spanning forest, circulant graph, Laplacian matrix, Chebyshev polynomial,
Mahler measure.
Math. Subj. Class. (2020): 05C30, 39A12
1 Introduction
The famous Kirchhoff’s Matrix Tree Theorem [15] states that the number of spanning
trees in a graph can be expressed as the product of its non-zero Laplacian eigenvalues
divided by the number of vertices. Since then, a lot of papers on enumeration of spanning
trees for various classes of graphs were published. In particular, explicit formulae were
derived for complete multipartite graphs [1, 5], almost complete graphs [33], wheels [3],
fans [12], prisms [2], ladders [26], Moebius ladders [27], lattices [28], anti-prisms [31],
*The authors are grateful to all the three anonymous referees for careful reading of manuscript and valuable
remarks and suggestions.
The authors were supported by the Mathematical Center in Akademgorodok, agreement no. 075-15-2019-1613
with the Ministry of Science and Higher Education of the Russian Federation.
†Corresponding author.
E-mail addresses: lfb o@yahoo.co.uk (Lilya A. Grunwald), ilyamednykh@mail.ru (Ilya Mednykh)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
676 Ars Math. Contemp. 22 (2022) #P4.10 / 675–686
complete prisms [25] and for many other families. For the circulant graphs some explicit
and recursive formulae are given in [8, 23, 34, 35].
Along with the number of spanning trees in a given graph one can be interested in the
number of rooted spanning forests in the graph. According to the classical result [14] (see
also more recent paper [7, 16]) this value can be found with the use of determinant of the
matrix det(I + L). Here L is the Laplacian matrix of the graph. At the same time, it is
known very little about analytic formulas for the number of spanning forests. In particular,
P. Chebotarev [6] enumerated the rooted spanning forests in path and cyclic graphs and O.
Knill [16] proved that the number of rooted spanning forests in the complete graph Kn on
n vertices is equal to (n+1)n−1. The rooted spanning forests in complete bipartite graphs
were enumerated in [13]. Explicit formulas for the number of rooted spanning forests for
cyclic, star, line and some other graphs were given by [16]. As for the number of unrooted
forests, it has much more complicated structure [4, 19, 32].
Starting with Boesch and Prodinger [3] the idea to apply Chebyshev polynomials for
counting various invariants of graphs arose. This idea provided a way to find complexity,
that is the number of spanning tress, of circulant graphs and their natural generalisations
in [8, 17, 23, 24, 35].
Recently, asymptotical behavior of complexity for some families of graphs was inves-
tigated from the point of view of so called Malher measure [11, 29]. Mahler measure of a
polynomial P (z), with complex coefficients, is the absolute value of the product of all the
roots of P (z) whose modulus is greater than 1 multiplied by the leading coefficient. For
general properties of the Mahler measure see survey [30] and monograph [10].
The purpose of this paper is to present new formulas for the number of rooted spanning
forests in circulant graphs and investigate their arithmetical properties and asymptotics.
We arrange the paper in the following way. First, in Sections 3 and 4, we present
new explicit formulas for the number of spanning forests in the undirected circulant graphs
Cn(s1, s2, . . . , sk) and C2n(s1, s2, . . . , sk, n) of even and odd valency respectively. They
will be given in terms of Chebyshev polynomials. Next, in Section 5, some arithmetic
properties of the number of spanning forests are investigated. More precisely, it is shown
that the number of spanning forests of the circulant graph G 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.
At last, in Section 6, we use explicit formulas for fG(n) in order to find its asymptotics
in terms of Mahler measure of the associated polynomials. For circulant graphs of even
valency the associated polynomial is P (z) = 2k + 1 −
∑k
j=1(z
sj + z−sj ). In this case
(Theorem 6.1) we have fG(n) ∼ An, n → ∞, where A is the Mahler measure of P (z).
For circulant graphs of odd valency we use the polynomial R(z) = P (z)(P (z) + 2). Then
the respective asymptotics (Theorem 6.2) is fG(n) ∼ Kn, n → ∞, where K = M(R). In
the last Section 7, we illustrate the obtained results by a series of examples.
2 Basic definitions and preliminary facts
Consider a finite and not necessary connected graph G without loops. A rooted tree is
a tree with one marked vertex called root. A rooted forest is a graph whose connected
components are rooted trees. A rooted spanning forest F in the graph G is a subgraph that
is a rooted forest containing all the vertices of G. We denote the vertex and edge set of G by
V (G) and E(G), respectively. Given u, v ∈ V (G), we set auv to be equal to the number
of edges between vertices u and v. The matrix A = A(G) = (auv)u, v∈V (G) is called the
L. A. Grunwaldr and I. Mednykh: The number of rooted forests in circulant graphs 677
adjacency matrix of the graph G. The degree d(v) of a vertex v ∈ V (G) is defined by
d(v) =
∑
u∈V (G) auv. Let D = D(G) be the diagonal matrix indexed by the elements of
V (G) with dvv = d(v). The matrix L = L(G) = D(G) − A(G) is called the Laplacian
matrix, or simply Laplacian, of the graph G.
By In we denote the identity matrix of order n.
Denote by χG(λ) = det(λIn − L(G)) the characteristic polynomial of the Laplacian
matrix of a graph G on n vertices. Its extended form is
χG(λ) = c1λ+ . . .+ cn−1λ
n−1 + λn.
The theorem by Kelmans and Chelnokov [14] states that the absolute value of coefficient
ck of χG(λ) coincides with the number of rooted spanning k-forests in the graph G. Since
all the Laplacian eigenvalues of G are non-negative, the sequence ck is alternating. So, the
number of rooted spanning forests of the graph G can be found by the formula
fG(n) = f1 + f2 + . . .+ fn = |c1 − c2 + c3 − . . .+ (−1)n−1| (2.1)
= (−1)nχG(−1) = det(In + L(G)).
This result was independently obtained by many authors (P. Chebotarev and E. Shamis [7]
O. Knill [16] and others).
Let s1, s2, . . . , sk be integers such that 1 ≤ s1 < s2 < . . . < sk ≤ n2 . The graph
Cn(s1, s2, . . . , sk) with n vertices 0, 1, 2, . . . , n− 1 is called circulant graph if the vertex
i, 0 ≤ i ≤ n−1 is adjacent to the vertices i±s1, i±s2, . . . , i±sk (mod n). When sk < n2
all vertices of the graph have even degree 2k. If n is even and sk = n2 , then all vertices
have odd degree 2k−1. Two circulant graphs Cn(s1, s2, . . . , sk) and Cn(s̃1, s̃2, . . . , s̃k) of
the same order are said to be conjugate by multiplier if there exists an integer r coprime to
n such that {s̃1, s̃2, ..., s̃k} = {rs1, rs2, . . . , rsk} as subsets of Zn. In this case, the graphs
are isomorphic, with multiplication by the unit r (modn) giving an isomorphism.
We call an n× n matrix circulant, and denote it by circ(a0, a1, . . . , an−1) if it is of the
form
circ(a0, a1, . . . , an−1) =

a0 a1 a2 . . . an−1
an−1 a0 a1 . . . an−2
...
. . .
...
a1 a2 a3 . . . a0

It is easy to see that adjacency and Laplacian matrices of the circulant graph are circu-
lant matrices. The converse is also true. If the Laplacian matrix of a graph is circulant then
the graph is also circulant.
Recall [9] that the eigenvalues of matrix C = circ(a0, a1, . . . , an−1) are given by
the following simple formulas λj = P (εjn), j = 0, 1, . . . , n − 1, where P (x) = a0 +
a1x + . . . + an−1x
n−1 and εn is an order n primitive root of unity. Moreover, the cir-
culant matrix T = circ(0, 1, 0, . . . , 0) is the matrix representation of the shift operator
T : (x0, x1, . . . , xn−2, xn−1) → (x1, x2, . . . , xn−1, x0).
Let P (z) = a0zs + . . . + as = a0
∏s
i=1(z − αi) be a nonconstant polynomial with
complex coefficients. Then, following Mahler [21] its Mahler measure is defined to be
M(P ) := exp(
∫ 1
0
log |P (e2πit)|dt), (2.2)
678 Ars Math. Contemp. 22 (2022) #P4.10 / 675–686
the geometric mean of |P (z)| for z on the unit circle. However, M(P ) had appeared earlier
in a paper by Lehmer [18], in an alternative form
M(P ) = |a0|
∏
|αi|>1
|αi|. (2.3)
See, for example [10], for the proof of equivalence of these definitions.
The concept of Mahler measure can be naturally extended to the class of Laurent poly-
nomials P (z) = a0zp+s+a1zp+s−1+. . .+as−1zs+1+aszs = a0zp
∏s
i=1(z−αi), where
a0 ̸= 0, s is a positive integer and p is an arbitrary and not necessarily positive integer.
Let Tn(z) = cos(n arccos z) be the Chebyshev polynomial of the first kind. The fol-
lowing property of the Chebyshev polynomials is widely used in the paper
Tn(
1
2 (z+ z
−1)) = 12 (z
n + z−n). See [22] for more properties of Chebyshev polynomials.
3 The number of rooted spanning forests of circulant graphs of even
valency
The aim of this section is to find new formulas for the numbers of rooted spanning forests
of circulant graph Cn(s1, s2, . . . , sk) in terms of Chebyshev polynomials. Here and below,
we will use G to denote the circulant graph under consideration.
Theorem 3.1. The number of rooted spanning forests fG(n) in the circulant graph
G = Cn(s1, s2, . . . , sk), 1 ≤ s1 < s2 < . . . < sk < n2 , is given by the formula
fG(n) =
sk∏
p=1
|2Tn(wp)− 2|,
where wp, p = 1, 2, . . . , sk are all the roots of the algebraic equation
∑k
j=1(2Tsj (w) −
2) = 1 and Ts(w) is the Chebyshev polynomial of the first kind.
Proof. The number of rooted spanning forests of the graph G can be found by the formula
fG(n) = det(In + L(G)). The latter value is equal to the product of all eigenvalues of
the matrix In + L(G). We denote by T = circ(0, 1, . . . , 0) the n× n cyclic shift operator.
Consider the Laurent polynomial P (z) = 2k + 1 −
∑k
i=1(z
si + z−si). Then the matrix
In + L(G) has the following form
In + L(G) = P (T ) = (2k + 1)In −
k∑
i=1
(T si + T−si).
The eigenvalues of circulant matrix T are εjn, j = 0, 1, . . . , n− 1, where εn = e
2πi
n . Since
all of them are distinct, the matrix T is similar to the matrix T = diag(1, εn, . . . , εn−1n )
with diagonal entries 1, εn, . . . , εn−1n . So the matrix In + L(G) is similar to the diagonal
matrix P (T). This essentially simplifies the problem of finding eigenvalues of In + L(G).
Indeed, let λ be an eigenvalue of P (T) and x be the corresponding eigenvector. Then we
have the following system of linear equations
((2k + 1− λ)In −
k∑
i=1
(Tsi + T−si))x = 0.
L. A. Grunwaldr and I. Mednykh: The number of rooted forests in circulant graphs 679
Recall that the matrices under consideration are diagonal and the (j + 1, j + 1)-th entry of
T is equal to εjn, where εn = e
2πi
n . Then, for any j = 0, . . . , n − 1, matrix P (T) has an
eigenvalue λj = P (εjn) = 2k + 1−
∑k
i=1(ε
jsi
n + ε
−jsi
n ). Hence we have
fG(n) =
n−1∏
j=0
P (εjn). (3.1)
To continue the proof of the theorem we need the following lemma.
Lemma 3.2.
n−1∏
j=0
P (εjn) =
sk∏
p=1
|2Tn(wp)− 2|,
where wp, p = 1, . . . , sk are all the roots of the algebraic equation
∑k
j=1(2Tsj (w)−2) =
1.
To prove the above formula we introduce integer polynomial P̃ (z) = −zskP (z). This
is a monic polynomial with the same roots as P (z) and its degree is 2sk. As P (z) = P ( 1z ),
its roots look like z1, 1z1 , . . . , zsk ,
1
zsk
.
We have
∏n−1
j=0 P (ε
j
n) =
∏n−1
j=0 (−ε−skjn P̃ (εjn)) = (−1)(sk+1)(n+1)−1
∏n−1
j=0 P̃ (ε
j
n).
Recall one of the basic properties of resultants
Res (P̃ (z), Q̃(z)) = (−1)deg(P̃ ) deg(Q̃)Res (Q̃(z), P̃ (z)),
where P̃ (z) and Q̃(z) are monic polynomials of degree deg(P̃ ) and deg(Q̃) respectively.
We set Q̃(z) = zn − 1 and note that deg(P̃ ) = 2sk is even. Then we obtain
n−1∏
j=0
P̃ (εjn) = Res (P̃ (z), z
n − 1) = Res (zn − 1, P̃ (z))
=
∏
z:P̃ (z)=0
(zn − 1) =
∏
z:P (z)=0
(zn − 1)
=
sk∏
p=1
(znp − 1)(z−np − 1) = (−1)sk
sk∏
p=1
(2Tn(wp)− 2).
We used the identity Tn( 12 (z + z
−1)) = 12 (z
n + z−n). Here wp = 12 (zp +
1
zp
),
p = 1, . . . , sk. These numbers are the roots of algebraic equation
∑k
j=1(2Tsj (w)−2) = 1.
To finish the proof of the theorem we use Lemma 3.2 and take absolute value of the
righthand side of the Equation 3.1.
4 The number of rooted spanning forests in circulant graphs of odd
valency
This section is devoted to investigation of the numbers of rooted spanning forests in circu-
lant graph C2n(s1, s2, . . . , sk, n) in terms of Chebyshev polynomials.
680 Ars Math. Contemp. 22 (2022) #P4.10 / 675–686
Theorem 4.1. Let C2n(s1, s2, . . . , sk, n), 1 ≤ s1 < s2 < . . . < sk < n, be a circulant
graph of odd degree. Then the number fG(n) of rooted spanning forests in the graph
G = C2n(s1, s2, . . . , sk, n) is given by the formula
fG(n) =
sk∏
p=1
(2Tn(up)− 2)(2Tn(vp) + 2),
where the numbers up and vp, p = 1, 2, . . . , sk are respectively the roots of the algebraic
equations Q(u)− 1 = 0 and Q(v) + 1 = 0, Q(w) = 2k + 2− 2
∑k
i=1 Tsi(w) and Ts(w)
is the Chebyshev polynomial of the first kind.
Proof. In order to find the number of rooted spanning forests fG(n) in the graph G we
need to find the determinant det(I2n + L(G)). The matrix I2n + L(G) can be represented
in the form
I2n + L(G) = (2k + 2)I2n −
k∑
j=1
(T sj + T−sj )− Tn,
where T is 2n × 2n circulant matrix circ(0, 1, 0, . . . , 0). The eigenvalues of circulant ma-
trix T are εj2n, j = 0, 1, . . . , 2n − 1, where ε2n = e
2πi
2n . Since all of them are distinct,
the matrix T is similar to the matrix T = diag(1, ε2n, . . . , ε2n−12n ) with diagonal entries
1, ε2n, . . . , ε
2n−1
2n . To find the determinant det(I2n + L(G)) we use the product of all
eigenvalues of matrix I2n+L(G). The matrix I2n+L(G) is similar to the diagonal matrix
with eigenvalues
λj = 2k + 2−
k∑
l=1
(εj sl2n + ε
−j sl
2n )− ε
jn
2n, j = 0, 1, . . . , 2n− 1.
All of them are non-zero.
Consider the following Laurent polynomial P (z) = 2k+2−
∑k
i=1(z
si +z−si). Since
εn2n = −1, we can write λj = P (ε
j
2n)− 1 if j is even and λj = P (ε
j
2n) + 1 if j is odd. By
Formula 2.1 we have
fG(n) =
2n−1∏
j=0
λj =
n−1∏
s=0
(P (ε2s2n)− 1)
n−1∏
s=0
(P (ε2s+12n ) + 1)
=
n−1∏
s=0
(P (ε2s2n)− 1)
∏2n−1
p=0 (P (ε
p
2n) + 1)∏n−1
s=0 (P (ε
2s
2n) + 1)
=
n−1∏
s=0
(P (εsn)− 1)
∏2n−1
p=0 (P (ε
p
2n) + 1)∏n−1
s=0 (P (ε
s
n) + 1)
.
By making use of Lemma 3.2 and arguments from the proof of Theorem 3.1 we obtain
(i)
∏n−1
s=0 (P (ε
s
n)− 1) = (−1)n (sk+1)
∏sk
p=1(2Tn(up)− 2),
(ii)
∏n−1
s=0 (P (ε
s
n) + 1) = (−1)n (sk+1)
∏sk
p=1(2Tn(vp)− 2), and
(iii)
∏2n−1
p=0 (P (ε
p
2n) + 1) =
∏sk
p=1(2T2n(vp)− 2),
L. A. Grunwaldr and I. Mednykh: The number of rooted forests in circulant graphs 681
where up and vp are the same as in the statement of the theorem. Hence,
fG(n) =
sk∏
p=1
(2Tn(up)− 2)
sk∏
p=1
T2n(vp)− 1
Tn(vp)− 1
.
Finally, taking into account the identity T2n(w)−1 = 2(Tn(w)−1)(Tn(w)+1) we obtain
fG(n) =
sk∏
p=1
(2Tn(up)− 2)(2Tn(vp) + 2).
5 Arithmetic properties of the number of rooted spanning forests for
circulant graphs
It has been proved in the paper [23] that the number of spanning trees τ(n) in circulant
graph Cn(s1, s2, . . . , sk) is given by the formula τ(n) = p n a(n)2, where a(n) is an
integer sequence and p is a natural number depending only on the parity of n. The aim of
the next theorem is to find a similar property for the number of rooted spanning forests.
Recall that any positive integer p can be uniquely represented in the form p = q r2,
where p and q are positive integers and q is square-free. We will call q the square-free part
of p.
Theorem 5.1. Let fG(n) be the number of rooted spanning forests in the circulant graph
Cn(s1, s2, . . . , sk), 1 ≤ s1 < s2 < . . . < sk <
n
2
.
Denote by p the number of odd elements in the sequence s1, s2, . . . , sk and let q be the
square-free part of 4p+ 1. Then there exists an integer sequence a(n) such that
(1) fG(n) = a(n)2, if n is odd;
(2) fG(n) = q a(n)2, if n is even.
Proof. The number of odd elements in the sequence s1, s2, . . . , sk is counted by the for-
mula p =
∑k
i=1
1−(−1)si
2 .
We already know that all eigenvalues of the In + L(G) are given by the formulas
λj = P (ε
j
n), j = 0, . . . , n−1, where P (z) = 2k+1−
∑k
i=1(z
si +z−si) and εn = e
2πi
n .
We note that λn−j = P (εn−jn ) = P (ε
j
n) = λj .
Since λ0 = P (ε0n) = P (1) = 1 by Formula 2.1 we have fG(n) =
∏n−1
j=1 λj . Since
λn−j = λj , we obtain fG(n) = (
∏n−1
2
j=1 λj)
2 if n is odd and fG(n) = λn2 (
∏n
2 −1
j=1 λj)
2 if n
is even. We note that each algebraic number λj comes with all its Galois conjugates [20].
So, the numbers b(n) =
∏n−1
2
j=1 λj and c(n) =
∏n
2 −1
j=1 λj are integers. Also, for even n we
have λn
2
= 2k + 1 −
∑k
i=1((−1)si + (−1)−si) = 1 + 2
∑k
i=1(1 − (−1)si) = 4p + 1.
Hence, fG(n) = b(n)2 if n is odd and fG(n) = (4p + 1) c(n)2 if n is even. Let q be
the square-free part of 4p + 1 and 4p + 1 = q r2. Setting a(n) = b(n) in the first case
and a(n) = r c(n) in the second, we conclude that number a(n) is always integer which
completes the proof.
682 Ars Math. Contemp. 22 (2022) #P4.10 / 675–686
The following theorem clarifies some number-theoretical properties of the number of
rooted spanning forests fG(n) for circulant graphs of odd valency.
Theorem 5.2. Let fG(n) be the number of rooted spanning forests in the circulant graph
G = C2n(s1, s2, . . . , sk, n), 1 ≤ s1 < s2 < . . . < sk < n.
Denote by p the number of odd elements in the sequence s1, s2, . . . , sk. Let q be the square-
free part of 4p + 1 and r be the square-free part of 4p + 3. Then there exists an integer
sequence a(n) such that
(1) fG(n) = q a(n)2, if n is even;
(2) fG(n) = r a(n)2, if n is odd.
Proof. The number p of odd elements in the sequence s1, s2, . . . , sk is equal to∑k
i=1
1−(−1)si
2 . The eigenvalues of the matrix I2n + L(G) are given by the formulas
λj = P (ε
j
2n)− (−1)j , j = 0, 1, . . . , 2n− 1,
where P (z) = 2k + 2−
∑k
l=1(z
sl + z−sl) and ε2n = e
πi
n .
Since λ0 = P (1) − 1 = 1 by the Formula 2.1 we have fG(n) =
∏2n−1
j=1 λj . Since
λ2n−j = λj , we obtain fG(n) = λn(
∏n−1
j=1 λj)
2, where λn = P (−1) − (−1)n. Now we
have
λn = 2k+2− (−1)n−2
k∑
l=1
(−1)sl = 2− (−1)n+4
k∑
l=1
1− (−1)sl
2
= 4 p+2− (−1)n.
So, λn = 4 p + 1, if n is even and λn = 4 p + 3, if n is odd. We note that each algebraic
number λj comes into the product
∏n−1
j=1 λj together with all its Galois conjugates, so the
number c(n) =
∏n−1
j=1 λj is an integer [20].
Hence, fG(n) = (4 p+ 1)c(n)2, if n is even and fG(n) = (4 p+ 3) c(n)2, if n is odd.
Let q and r be the square-free parts of 4 p + 1 and of 4p + 3 respectively. Then for some
integers x and y we have 4 p+ 1 = q x2 and 4 p+ 3 = r y2.
Now, the integer number fG(n) can be represented in the form
(1) fG(n) = q (x c(n))2 if n is even and
(2) fG(n) = r (y c(n))2 if n is odd.
Setting a(n) = x c(n) in the first case and a(n) = y c(n) in the second, we conclude that
number a(n) is always integer. The theorem is proved.
6 Asymptotics for the number of spanning forests
In this section we give asymptotic formulas for the number of rooted spanning forests in
circulant graphs.
Theorem 6.1. The number of rooted spanning forests in the circulant graph
G = Cn(s1, s2, . . . , sk), 1 ≤ s1 < s2 < . . . < sk <
n
2
L. A. Grunwaldr and I. Mednykh: The number of rooted forests in circulant graphs 683
has the following asymptotics
fG(n) ∼ An, as n → ∞
where A = exp(
∫ 1
0
log(P (e2πit))dt) is the Mahler measure of Laurent polynomial
P (z) = 2k + 1−
∑k
i=1(z
si + z−si).
Proof. By Theorem 3.1, the number of rooted spanning forests fG(n) is given by
fG(n) =
sk∏
s=1
|2Tn(ws)− 2|,
where ws = (zs + z−1s )/2. We have Tn(ws) =
1
2 (z
n
s + z
−n
s ), where zs and 1/zs,
s = 1, . . . , sk are all the roots of the polynomial P (z). If φ ∈ R then P (eiφ) =
2k + 1 −
∑k
j=1(e
sjiφ + e−sjiφ) = 2k + 1 − 2
∑k
j=1 cos(sjφ) ≥ 1, so |zs| ≠ 1 for
all s. Replacing zs by 1/zs, if it is necessary, we can assume that |zs| > 1 for all s. Then
Tn(ws) ∼ 12z
n
s , as n tends to ∞. So, |2Tn(ws)− 2| ∼ |zs|n, n → ∞. Hence
sk∏
s=1
|2Tn(ws)− 2| ∼
sk∏
s=1
|zs|n =
∏
P (z)=0, |z|>1
|z|n = An,
where A =
∏
P (z)=0, |z|>1 |z| is the Mahler measure of P (z). By the results mentioned in
the preliminary part, it can be found by the formula A = exp(
∫ 1
0
log(P (e2πit))dt).
Finally,
fG(n) =
sk∏
s=1
|2Tn(ws)− 2| ∼ An, n → ∞.
The next theorem is a direct consequence of Theorem 4.1 and can be proved by the
same arguments as Theorem 6.1.
Theorem 6.2. The number of rooted spanning forests fG(n) in the circulant graph
G = C2n(s1, s2, . . . , sk, n), 1 ≤ s1 < s2 < . . . < sk < n has the following asymp-
totics
fG(n) ∼ Kn, as n → ∞.
Here K = exp(
∫ 1
0
log |P (e2πit)2−1|dt) is the Mahler measure of the Laurent polynomial
P (z)2 − 1, where P (z) = 2k + 2−
∑k
i=1(z
si + z−si).
7 Examples
(1) Cycle graph G = Cn(1) = Cn.
We need to solve the equation 1+2− 2T1(w) = 0. We have w = 3/2. So, fG(n) =
2Tn(3/2) − 2. Then fG(n) ∼
n→∞
( 3+
√
5
2 )
n. Also, we have fG(n) = 5F 2n , if n is
even, and fG(n) = L2n, if n is odd, where Fn and Ln are the Fibonacci and Lucas
numbers respectively. The latter result was independently obtained in [6].
684 Ars Math. Contemp. 22 (2022) #P4.10 / 675–686
(2) Graph G = Cn(1, 2).
We need to solve the equation 1 + 4 − 2T1(w) − 2T2(w) = 0. Its roots are w1 =
1
4 (−1 +
√
29) and w2 = 14 (−1−
√
29).
By Theorem 5.1, there exists an integer sequence a(n) such that fG(n) = 5a(n)2, if
n is even, and fG(n) = a(n)2, if n is odd.
(3) Graph G = Cn(1, 3).
Let w1, w2 and w3 be the roots of the cubic equation 1+4−2T1(w)−2T3(w) = 0.
Then fG(n) = (2Tn(w1)− 2)(2Tn(w2)− 2)(2Tn(w3)− 2). In this case, fG(n) ∼
An1,3, n → ∞, where A1,3 ≈ 4.48461 . . . is the Mahler measure of the Laurent
polynomial 5−z−z−1−z3−z−3. One can check that A1,3 is a root of the equation
1−x− 2x2− 4x3+x4 = 0. By Theorem 5.1, we have fG(n) = a(n)2, where a(n)
is an integer sequence.
(4) Graph Möbius ladder G = C2n(1, n).
We have to solve the equations 3−2T1(w) = 0 and 5−2T1(w) = 0. Their roots are
u1 = 3/2 and v1 = 5/2 respectively. Then fG(n) = (2Tn(3/2) − 2)(2Tn(5/2) +
2) ∼ Kn, where K = 14 (3 +
√
5)(5 +
√
21) ≈ 12.5438 . . . . By Theorem 5.2,
fG(n) = 5a(n)
2, if n is even, and fG(n) = 7a(n)2, if n is odd for some integer
sequence a(n).
ORCID iDs
Lilya A. Grunwald https://orcid.org/0000-0003-4622-5259
Ilya Mednykh https://orcid.org/0000-0001-7682-3917
References
[1] T. L. Austin, The enumeration of point labelled chromatic graphs and trees, Can. J. Math. 12
(1960), 535–545, doi:10.4153/cjm-1960-047-1.
[2] F. T. Boesch and Z. R. Bogdanowicz, The number of spanning trees in a prism, Int. J. Comput.
Math. 21 (1987), 229–243, doi:10.1080/00207168708803568.
[3] F. T. Boesch and H. Prodinger, Spanning tree formulas and Chebyshev polynomials, Graphs
Comb. 2 (1986), 191–200, doi:10.1007/bf01788093.
[4] D. Callan, A combinatorial derivation of the number of labeled forests, J. Integer Seq. 6 (2003),
Article 03.4.7, 9, https://cs.uwaterloo.ca/journals/JIS/vol6.html.
[5] A. Cayley, A theorem on trees, Quart. J. Pure Appl. Math. 23 (1889), 376–378.
[6] P. Chebotarev, Spanning forests and the golden ratio, Discrete Appl. Math. 156 (2008), 813–
821, doi:10.1016/j.dam.2007.08.030.
[7] P. Chebotarev and E. Shamis, Matrix forest theorems, 2006, arXiv:math/0602575
[math.CO].
[8] X. Chen, Q. Lin and F. Zhang, The number of spanning trees in odd valent circulant graphs,
Discrete Math. 282 (2004), 69–79, doi:10.1016/j.disc.2003.12.006.
[9] P. J. Davis, Circulant Matrices, New York, NY: AMS Chelsea Publishing, 1994.
[10] G. Everest and T. Ward, Heights of polynomials and entropy in algebraic dynamics, Universi-
text, Springer-Verlag London, Ltd., London, 1999, doi:10.1007/978-1-4471-3898-3.
L. A. Grunwaldr and I. Mednykh: The number of rooted forests in circulant graphs 685
[11] A. J. Guttmann and M. D. Rogers, Spanning tree generating functions and Mahler measures, J.
Phys. A 45 (2012), 494001, 24, doi:10.1088/1751-8113/45/49/494001.
[12] A. J. W. Hilton, Spanning trees and Fibonacci and Lucas numbers, Fibonacci Quart. 12 (1974),
259–262, https://www.fq.math.ca/12-3.html.
[13] Y. Jin and C. Liu, Enumeration for spanning forests of complete bipartite graphs, Ars Comb. 70
(2004), 135–138, https://www.researchgate.net/publication/220620306_
Enumeration_for_spanning_forests_of_complete_bipartite_graphs.
[14] A. K. Kelmans and V. M. Chelnokov, A certain polynomial of a graph and graphs with
an extremal number of trees, J. Comb. Theory Ser. B 16 (1974), 197–214, doi:10.1016/
0095-8956(74)90065-3.
[15] G. Kirchhoff, Über die auflösung der gleichungen, auf welche man bei der untersuchung der
linearen verteilung galvanischer ströme geführt wird,, Ann. Phys. Chem. 72 (1847), 497–508,
doi:10.1002/andp.18471481202.
[16] O. Knill, Cauchy-Binet for pseudo-determinants, Linear Algebra Appl. 459 (2014), 522–547,
doi:10.1016/j.laa.2014.07.013.
[17] Y. S. Kwon, A. D. Mednykh and I. A. Mednykh, On Jacobian group and complexity of the
generalized Petersen graph GP(n, k) through Chebyshev polynomials, Linear Algebra Appl.
529 (2017), 355–373, doi:10.1016/j.laa.2017.04.032.
[18] D. H. Lehmer, Factorization of certain cyclotomic functions., Ann. Math. (2) 34 (1934), 461–
479, doi:10.2307/1968172.
[19] C. J. Liu and Y. Chow, Enumeration of forests in a graph, Proc. Am. Math. Soc. 83 (1981),
659–662, doi:10.2307/2044142.
[20] D. Lorenzini, Smith normal form and Laplacians, J. Comb. Theory, Ser. B 98 (2008), 1271–
1300, doi:10.1016/j.jctb.2008.02.002.
[21] K. Mahler, On some inequalities for polynomials in several variables, J. Lond. Math. Soc. 37
(1962), 341–344, doi:10.1112/jlms/s1-37.1.341.
[22] J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Boca Raton, FL: Chapman &
Hall/CRC, 2003, http://inis.jinr.ru/sl/.
[23] A. D. Mednykh and I. A. Mednykh, The number of spanning trees in circulant graphs, its
arithmetic properties and asymptotic, Discrete Math. 342 (2019), 1772–1781, doi:10.1016/j.
disc.2018.08.030.
[24] I. A. Mednykh, On Jacobian group and complexity of I-graph I(n, k, l) through Chebyshev
polynomials, Ars Math. Contemp. 15 (2018), 467–485, doi:10.26493/1855-3974.1355.576.
[25] A. J. Schwenk, Computing the characteristic polynomial of a graph, Graphs Comb. 406 (1974),
153–172, doi:10.1007/bfb0066438.
[26] J. Sedlacek, On the spanning trees of finite graphs, Čas. Pěstovánı́ Mat. 91 (1966), 221–226.
[27] J. Sedlacek, On the skeletons of a graph or digraph, Combinat. Struct. Appl.,
1970, https://www.researchgate.net/publication/265917830_On_the_
skeletons_of_a_graph_or_digraph.
[28] R. Shrock and F. Y. Wu, Spanning trees on graphs and lattices in d-dimensions, J. Phys. A,
Math. Gen. 33 (2000), 3881–3902, doi:10.1088/0305-4470/33/21/303.
[29] D. S. Silver and S. G. Williams, Graph complexity and mahler measure, 2017,
arXiv:1701.06097v1 [math.CO].
[30] C. Smyth, The Mahler measure of algebraic numbers: a survey, in: Number Theory and
Polynomials, Cambridge: Cambridge University Press, pp. 322–349, 2010, doi:10.1017/
cbo9780511721274.021.
686 Ars Math. Contemp. 22 (2022) #P4.10 / 675–686
[31] W. Sun, S. Wang and J. Zhang, Counting spanning trees in prism and anti-prism graphs, J.
Appl. Anal. Comput. 6 (2016), 65–75, doi:10.11948/2016006.
[32] L. Takács, On the number of distinct forests, SIAM J. Discrete Math. 3 (1990), 574–581, doi:
10.1137/0403050.
[33] L. Weinberg, Number of trees in graph, Proc. IRE 46 (1958), 1954–1955.
[34] Y. Zhang, X. Yong and M. J. Golin, The number of spanning trees in circulant graphs, Discrete
Math. 223 (2000), 337–350, doi:10.1016/s0012-365x(99)00414-8.
[35] Y. Zhang, X. Yong and M. J. Golin, Chebyshev polynomials and spanning tree formulas for
circulant and related graphs, Discrete Math. 298 (2005), 334–364, doi:10.1016/j.disc.2004.10.
025.