ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.08
https://doi.org/10.26493/1855-3974.2530.e7c
(Also available at http://amc-journal.eu)
Complexity of circulant graphs with non-fixed
jumps, its arithmetic properties and
asymptotics*
Alexander Mednykh , Ilya Mednykh †
Sobolev Institute of Mathematics, 630090, Novosibirsk, Russia
Novosibirsk State University, 630090, Novosibirsk, Russia
Received 11 January 2021, accepted 23 March 2022, published online 21 October 2022
Abstract
In the present paper, we investigate a family of circulant graphs with non-fixed jumps
Gn = Cβn(s1, . . . , sk, α1n, . . . , αℓn),
1 ≤ s1 < . . . < sk < [
βn
2
], 1 ≤ α1 < . . . < αℓ ≤ [
β
2
].
Here n is an arbitrary large natural number and integers s1, . . . , sk, α1, . . . , αℓ, β are sup-
posed to be fixed.
First, we present an explicit formula for the number of spanning trees in the graph Gn.
This formula is a product of βsk−1 factors, each given by the n-th Chebyshev polynomial
of the first kind evaluated at the roots of some prescribed polynomial of degree sk. Next, we
provide some arithmetic properties of the complexity function. We show that the number
of spanning trees in Gn can be represented in the form τ(n) = p n a(n)2, where a(n)
is an integer sequence and p is a given natural number depending on parity of β and n.
Finally, we find an asymptotic formula for τ(n) through the Mahler measure of the Laurent
polynomials differing by a constant from 2k −
∑k
i=1(z
si + z−si).
Keywords: Spanning tree, circulant graph, Laplacian matrix, Chebyshev polynomial, Mahler mea-
sure.
Math. Subj. Class. (2020): 05C30, 05A18
*The authors are grateful to anonymous referees for helpful remarks and suggestions. The work was supported
by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1613 with the Ministry of Science
and Higher Education of the Russian Federation.
†Corresponding author.
E-mail addresses: smedn@mail.ru (Alexander Mednykh), ilyamednykh@mail.ru (Ilya Mednykh)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P1.08
1 Introduction
The complexity of a finite connected graph G, denoted by τ(G), is the number of span-
ning trees of G. The famous Kirchhoff’s Matrix Tree Theorem [13] states that τ(G) can
be expressed as the product of non-zero Laplacian eigenvalues of G divided by the number
of its vertices. Since then, a lot of papers devoted to the complexity of various classes of
graphs were published. In particular, explicit formulae were derived for complete multipar-
tite graphs [16], wheels [2], fans [10], prisms [1], anti-prisms [32], ladders [26], Möbius
ladders [27], lattices [28] and other families. The complexity of circulant graphs has been
the subject of study by many authors [4, 5, 17, 34, 35, 36, 37, 38].
Starting with Boesch and Prodinger [2] the idea to calculate the complexity of graphs by
making use of Chebyshev polynomials was implemented. This idea provided a way to find
complexity of circulant graphs and their natural generalisations in [4, 14, 19, 25, 36, 38].
Recently, asymptotical behavior of complexity for some families of graphs was investi-
gated from the point of view of so called Malher measure [9, 29, 30]. For general properties
of the Mahler measure see, for example [31] and [7]. It worth mentioning that the Mahler
measure is related to the growth of groups, values of some hypergeometric functions and
volumes of hyperbolic manifolds [3].
For a sequence of graphs Gn, one can consider the number of vertices v(Gn) and the
number of spanning trees τ(Gn) as functions of n. Assuming that limn→∞
log τ(Gn)
v(Gn)
exists,
it is called the thermodynamic limit of the family Gn [20]. This number plays an important
role in statistical physics and was investigated by many authors [12, 28, 29, 30, 33].
The purpose of this paper is to present new formulas for the number of spanning trees
in circulant graphs with non-fixed jumps and investigate their arithmetical properties and
asymptotics. We mention that the number of spanning trees for such graphs was found
earlier in [5, 8, 17, 19, 37, 38]. Our results are different from those obtained in the cited
papers. Moreover, by the authors opinion, the obtained formulas are more convenient for
analytical investigation.
The content of the paper is lined up as follows. Basic definitions and preliminary results
are given in Sections 2 and 3. Then, in the Section 4, we present an explicit formula for the
number of spanning trees in the undirected circulant graph
Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn),
1 ≤ s1 < . . . < sk < [
βn
2
], 1 ≤ α1 < . . . < αℓ ≤ [
β
2
].
This formula is a product of βsk−1 factors, each given by the n-th Chebyshev polynomial
of the first kind evaluated at the roots of a prescribed polynomial of degree sk. Through the
paper, we will assume that β > 1 and ℓ > 0. The case β = 1 and ℓ = 0 of the circulant
graphs with bounded jumps has been investigated in our previous papers [22, 23].
Next, in the Section 5, we provide some arithmetic properties of the complexity func-
tion. More precisely, we show that the number of spanning trees of the circulant graph can
be represented in the form τ(n) = β pn a(n)2, where a(n) is an integer sequence and p is a
prescribed natural number depending only on parity of n and β. Later, in the Section 6, we
use explicit formulas for the number of spanning trees to produce its asymptotics through
the Mahler measures of the finite set of Laurent polynomials
Pu(z) = 2k −
k∑
i=1
(zsi + z−si) + 4
ℓ∑
m=1
sin2(
π uαm
β
), u = 0, 1, . . . , β − 1.
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 3
As a consequence (Corollary 6.2), we prove that the thermodynamic limit of sequence
Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn) as n → ∞ is the arithmetic mean of small Mahler
measures of Laurent polynomials Pu(z), u = 0, 1, . . . , β−1. In the Section 7, we illustrate
the obtained results by a series of examples.
2 Basic definitions and preliminary facts
Consider a connected finite graph G, allowed to have multiple edges but without loops. 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 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.
In what follows, by In we denote the identity matrix of order n.
Let s1, s2, . . . , sk be integers such that 1 ≤ s1, s2, . . . , sk ≤ n2 . The graph
G = 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). All
vertices of the graph G have even degree 2k. If there is i such that si = n2 then graph G
has multiple edges.
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 easy to chose enumeration of vertices such that adjacency and Laplacian matrices for
the circulant graph are circulant matrices. The converse is also true. If the Laplacian matrix
of a graph is circulant then the graph is also circulant.
In this paper, we consider a particular class of circulant graphs, namely circulant graphs
with non-fixed jumps. They are defined as before, with special restrictions on the number
of vertices and structure of jumps.
More precisely, we will deal with circulant graphs
Gn = Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn)
on β n vertices and jumps s1, s2, . . . , sk, α1n, α2n, . . . , αℓn satisfying the inequalities
1 ≤ s1 < . . . < sk < [βn2 ], 1 ≤ α1 < . . . < αℓ ≤ [
β
2 ]. Mostly, we are interest-
ing in investigation of such graphs for sufficiently large n. In what follows, the numbers
s1, s2, . . . , sk, α1, α2, . . . , αℓ, β are supposed to be fixed positive integers.
In particular, graph Gn has no multiple edges if αℓ < β2 . If αℓ =
β
2 , it has exactly
two edges between vertices vi and vi+ β n2 , where indices are taken mod β n. In the latter
case, β is certainly an even positive integer. A typical example is graph C2n(1, n) which,
under the above agreement, represents a Moebius ladder graph on 2n vertices with double
steps. Circulant graphs with non-fixed jumps have been the subject of investigation in many
papers [8, 17, 24, 38].
4 Ars Math. Contemp. 23 (2023) #P1.08
Warning. In series of papers [5, 22, 23, 37] devoted to circulant graphs with odd
degree of vertices the notation C2n(1, n) stands for the Moebius ladder with ordinary steps.
The degree of vertices of such graph is three. These families of graphs are outside of
consideration in the present paper.
Recall [6] that the eigenvalues of matrix C = circ(a0, a1, . . . , an−1) are given by the
following simple formulas λj = L(ζjn), j = 0, 1, . . . , n − 1, where L(x) = a0 + a1x +
. . . + an−1x
n−1 and ζn is a primitive n-th root of unity. Moreover, the circulant matrix
C = L(T ), where 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) = a0 + a1z+ . . .+ adzd = ad
∏d
k=1(z−αk) be a non-constant 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.1)
the geometric mean of |P (z)| for z on the unit circle. However, M(P ) had appeared earlier
in a paper by Lehmer [15], in an alternative form
M(P ) = |ad|
∏
|αk|>1
|αk|. (2.2)
The equivalence of the two definitions follows immediately from Jensen’s formula [11]∫ 1
0
log |e2πit − α|dt = log+ |α|,
where log+ x denotes max(0, log x). We will also deal with the small Mahler measure
which is defined as
m(P ) := logM(P ) =
∫ 1
0
log |P (e2πit)|dt.
The concept of Mahler measure can be naturally extended to the class of Laurent polyno-
mials P (z) = a0zp+a1zp+1+ . . .+ad−1zp+d−1+adzp+d = adzp
∏d
k=1(z−αk), where
a0, ad ̸= 0 and p is an arbitrary and not necessarily positive integer.
3 Associated polynomials and their properties
The aim of this section is to introduce a few polynomials naturally associated with the
circulant graph
Gn = Cβn(s1, . . . , sk, α1n, . . . , αℓn),
1 ≤ s1 < . . . < sk < [
βn
2
], 1 ≤ α1 < . . . < αℓ ≤ [
β
2
].
We start with the Laurent polynomial
L(z) = 2(k + ℓ)−
k∑
i=1
(zsi + z−si)−
ℓ∑
m=1
(zαmn + z−αmn)
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 5
responsible for the structure of Laplacian of graph Gn. More precisely, the Laplacian of
Gn is given by the matrix
L = L(T ) = 2(k + ℓ)Iβn −
k∑
i=1
(T si + T−si)−
ℓ∑
m=1
(Tαmn + T−αmn),
where T the circulant matrix circ(0, 1, . . . , 0︸ ︷︷ ︸
βn
). We decompose L(z) into the sum of two
polynomials L(z) = P (z) + p(zn), where P (z) = 2k −
∑k
i=1(z
si + z−si) and
p(z) = 2ℓ −
∑ℓ
m=1(z
αm + z−αm). Now, we have to introduce a family of Laurent poly-
nomials differing by a constant from P (z). They are Pu(z) = P (z) + p(e
2π i u
β ), u =
0, 1, . . . , β−1. One can check that Pu(z) = 2k−
∑k
i=1(z
si+z−si)+4
∑ℓ
m=1 sin
2(π uαmβ ).
In particular, P0(z) = P (z).
We note that all the above Laurent polynomials are palindromic, that is they are invari-
ant under replacement z by 1/z. Any non-trivial palindromic Laurent polynomial can be
represented in the form P(z) = asz−s+as−1z−(s−1)+ . . .+a0+ . . .+as−1zs−1+aszs,
where as ̸= 0. We will refer to 2s as a degree of the polynomial P(z). Since P(z) = P( 1z ),
the following polynomial of degree s is well defined
Q(w) = P(w +
√
w2 − 1).
We will call it a Chebyshev trasform of P(z). Since Tk(w) = (w+
√
w2−1)k+(w+
√
w2−1)−k
2
is the k-th Chebyshev polynomial of the first kind, one can easy deduce that
Q(w) = a0 + 2a1T1(w) + . . .+ 2as−1Ts−1(w) + 2asTs(w).
Also, we have P(z) = Q( 12 (z +
1
z )).
Throughout the paper, we will use the following observation. If z1, 1/z1, . . . , zs, 1/zs
is the list of all the roots of P(z), then wk = 12 (zk +
1
zk
), k = 1, 2, . . . , s are all the roots
of the polynomial Q(w).
By direct calculation, we obtain that the Chebyshev transform of polynomial Pu(z) is
Qu(w) = 2k − 2
k∑
i=1
Tsi(w) + 4
ℓ∑
m=1
sin2(
π uαm
β
).
In particular, if zs(u), 1/zs(u), s = 1, 2, . . . , sk are the roots of Pu(z), then
ws(u) =
1
2 (zs(u) + zs(u)
−1), s = 1, 2, . . . , sk are all roots of the algebraic equation∑k
i=1 Tsi(w) = k + 2
∑ℓ
m=1 sin
2(π uαmβ ). We also need the following lemma.
Lemma 3.1. Let gcd(α1, α2, . . . , αℓ, β) = 1. Suppose that Pu(z) = 0, where 0 < u < β.
Then |z| ≠ 1.
Proof. Recall that Pu(z) = P (z)+ p(e
2π i u
β ), where P (z) = 2k−
∑k
i=1(z
si + z−si) and
p(z) = 2ℓ−
∑ℓ
m=1(z
αm + z−αm). We show that p(e
2π i u
β ) = 4
∑ℓ
m=1 sin
2(π uαmβ ) > 0.
Indeed, suppose that p(e
2π i u
β ) = 0. Then there are integers mj such that uαj = mjβ, j =
1, 2, . . . , ℓ. Hence
B = gcd(uα1, . . . , u αℓ, u β) = u gcd(α1, . . . , αℓ, β) = u < β.
6 Ars Math. Contemp. 23 (2023) #P1.08
From the other side
B = gcd(m1β, . . . ,mℓβ, u β) = β gcd(m1, . . . ,mℓ, u) ≥ β.
Contradiction. Now, let |z| = 1. Then z = eiφ, for some φ ∈ R. We have
Pu(e
iφ) = P (eiφ) + p(e
2π i u
β ) = 2k −
k∑
j=1
(eisjφ + e−isjφ) + 4
ℓ∑
m=1
sin2(
π uαm
β
)
= 2
k∑
j=1
(1− cos(sjφ)) + 4
ℓ∑
m=1
sin2(
π uαm
β
) > 0.
Hence, Pu(z) > 0 and lemma is proved.
4 Complexity of circulant graphs with non-fixed jumps
The aim of this section is to find new formulas for the numbers of spanning trees of circu-
lant graph Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn) in terms of Chebyshev polynomials. It
should be noted that nearby results were obtained earlier by different methods in the papers
[5, 8, 17, 19, 37, 38].
Theorem 4.1. The number of spanning trees in the circulant graph with non-fixed jumps
Cβn(s1, . . . , sk, α1n, . . . , αℓn), 1 ≤ s1 < . . . < sk < [
βn
2
], 1 ≤ α1 < . . . < αℓ ≤ [
β
2
]
is given by the formula
τ(n) =
n
β q
β−1∏
u=0
sk∏
j=1,
wj(0)̸=1
|2Tn(wj(u))− 2 cos(
2πu
β
)|,
where for each u = 0, 1, . . . , β − 1 the numbers wj(u), j = 1, 2, . . . , sk, are all the
roots of the equation
∑k
i=1 Tsi(w) = k + 2
∑ℓ
m=1 sin
2(π uαmβ ), Ts(w) is the Chebyshev
polynomial of the first kind and q = s21 + s
2
2 + . . .+ s
2
k.
Proof. Let G = Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn). By the celebrated Kirchhoff the-
orem, the number of spanning trees τ(n) in Gn is equal to the product of non-zero eigen-
values of the Laplacian of the graph Gn divided by the number of its vertices βn. To
investigate the spectrum of Laplacian matrix, we denote by T the βn×βn circulant matrix
circ(0, 1, . . . , 0). Consider the Laurent polynomial
L(z) = 2(k + ℓ)−
k∑
i=1
(zsi + z−si)−
ℓ∑
m=1
(zαmn + z−αmn).
Then the Laplacian of Gn is given by the matrix
L = L(T ) = 2(k + ℓ)Iβn −
k∑
i=1
(T si + T−si)−
ℓ∑
m=1
(Tαmn + T−αmn).
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 7
The eigenvalues of the circulant matrix T are ζjβn, j = 0, 1, . . . , βn − 1, where ζℓ =
e
2πi
ℓ . Since all of them are distinct, the matrix T is similar to the diagonal matrix T =
diag(1, ζβn, . . . , ζ
βn−1
βn ). To find spectrum of L, without loss of generality, one can assume
that T = T. Then L is a diagonal matrix. This essentially simplifies the problem of finding
eigenvalues of L. Indeed, let λ be an eigenvalue of L and x be the respective eigenvector.
Then we have the following system of linear equations
((2(k + ℓ)− λ)Iβn −
k∑
i=1
(T si + T−si)−
ℓ∑
m=1
(Tαmn + T−αmn))x = 0.
Let ej = (0, . . . , 1︸︷︷︸
j−th
, . . . , 0), j = 1, . . . , βn. The (j, j)-th entry of T is equal to ζj−1βn .
Then, for j = 0, . . . , βn− 1, the matrix L has an eigenvalue
λj = L(ζ
j
βn) = 2(k + ℓ)−
k∑
i=1
(ζjsiβn + ζ
−jsi
βn )−
ℓ∑
m=1
(ζjαmβ + ζ
−jαm
β ), (4.1)
with eigenvector ej+1. Since all graphs under consideration are supposed to be connected,
we have λ0 = 0 and λj > 0, j = 1, 2, . . . , βn− 1. Hence
τ(n) =
1
βn
βn−1∏
j=1
L(ζjβn). (4.2)
By setting j = βt+ u, where 0 ≤ t ≤ n− 1, 0 ≤ u ≤ β − 1, we rewrite the formula
(4.2) in the form
τ(n) = (
1
n
n−1∏
t=1
L(ζβtβn))(
1
β
β−1∏
u=1
n−1∏
t=0
L(ζtβ+uβn )). (4.3)
It is easy to see that τ(n) is the product of two numbers τ1(n) = 1n
∏n−1
t=1 L(ζ
βt
βn) and
τ2(n) =
1
β
∏β−1
u=1
∏n−1
t=0 L(ζ
tβ+u
βn ).
We note that
L(ζβtβn) = 2k −
k∑
i=1
(ζβtsiβn + ζ
−βtsi
βn ) = 2k −
k∑
i=1
(ζtsin + ζ
−tsi
n ) = P (ζ
t
n), 1 ≤ t ≤ n− 1.
The numbers µt = P (ζtn), 1 ≤ t ≤ n−1 run through all non-zero Laplacian eigenvalues of
circulant graph Cn(s1, s2, . . . , sk) with fixed jumps s1, s2, . . . , sk and n vertices. So τ1(n)
coincide with the number of spanning trees in Cn(s1, s2, . . . , sk). By ([23], Corollary 1)
we get
τ1(n) =
n
q
sk∏
j=1,
wj(0)̸=1
|2Tn(wj(0))− 2|, (4.4)
where wj(0), j = 1, 2, . . . , sk, are all the roots of the equation
∑k
i=1 Tsi(w) = k.
8 Ars Math. Contemp. 23 (2023) #P1.08
In order to continue the calculation of τ(n) we have to find the product
τ2(n) =
1
β
β−1∏
u=1
n−1∏
t=0
L(ζtβ+uβn ).
Recall that L(z) = P (z) + p(zn). Since (ζβt+uβn )
n = ζβt+uβ = ζ
u
β , we obtain
L(ζβt+uβn ) = P (ζ
βt+u
βn ) + p(ζ
βt+u
β ) = P (ζ
βt+u
βn ) + p(ζ
u
β ) = Pu(ζ
βt+u
βn ),
where Pu(z) = P (z) + p(ζuβ ). By Section 3, we already know that
Pu(z) = −
sk∏
j=1
(z − zj(u))(z − zj(u)−1),
where wj(u) = 12 (zj(u) + zj(u)
−1), j = 1, 2, . . . , sk are all roots of the equation∑k
i=1 Tsi(w) = k + 2
∑ℓ
d=1 sin
2(π uαdβ ).
We note that ζtβ+uβn = e
i(2πt+ωu)
n , where ωu = 2πuβ . Then
∏n−1
t=0 L(ζ
tβ+u
βn ) =∏n−1
t=0 Pu(e
i(2πt+ωu)
n ). To evaluate the latter product, we need following lemma.
Lemma 4.2. Let H(z) =
∏m
s=1(z − zs)(z − z−1s ) and ω be a real number. Then
n−1∏
t=0
H(e
i(2πt+ω)
n ) = (−eiω)m
m∏
s=1
(2Tn(ws)− 2 cos(ω)),
where ws = 12 (zs + z
−1
s ), s = 1, . . . ,m and Tn(w) is the n-th Chebyshev polynomial of
the first kind.
Proof of Lemma 4.2. We note that 12 (z
n + z−n) = Tn(
1
2 (z + z
−1)). By the substitution
z = ei φ, this follows from the evident identity cos(nφ) = Tn(cosφ). Then we have
n−1∏
t=0
H(e
i(2πt+ω)
n ) =
n−1∏
t=0
m∏
s=1
(e
i(2πt+ω)
n − zs)(e
i(2πt+ω)
n − z−1s )
=
m∏
s=1
n−1∏
t=0
(−e
i(2πt+ω)
n z−1s )(zs − e
i(2πt+ω)
n )(zs − e−
i(2πt+ω)
n )
=
m∏
s=1
(−eiωzs−n)
n−1∏
t=0
(zs − e
i(2πt+ω)
n )(zs − e−
i(2πt+ω)
n )
=
m∏
s=1
(−eiωzs−n)(z2ns − 2 cos(ω)zns + 1)
=
m∏
s=1
(−eiω)(2 z
n
s + z
−n
s
2
− 2 cos(ω))
= (−eiω)m
m∏
s=1
(2Tn(ws)− 2 cos(ω)).
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 9
Since Pu(z) = −Hu(z), where Hu(z) =
∏sk
j=1(z−zj(u))(z−zj(u)−1), by Lemma 4.2
we get
n−1∏
t=0
Pu(e
i(2πt+ωu)
n ) = (−1)n(−e
2π i u
β )sk
sk∏
j=1
(2Tn(wj(u))− 2 cos(
2π u
β
)).
Then,
τ2(n) =
1
β
β−1∏
u=1
n−1∏
t=0
L(ζβt+uβn ) =
1
β
β−1∏
u=1
n−1∏
t=0
Pu(e
i(2πj+ωu)
n )
=
(−1)n(β−1)
β
β−1∏
u=1
(−e
2π i u
β )sk
sk∏
j=1
(2Tn(wj(u))− 2 cos(
2π u
β
)) (4.5)
=
(−1)n(β−1)
β
β−1∏
u=1
sk∏
j=1
(2Tn(wj(u))− 2 cos(
2π u
β
)).
Since the number τ2(n) is a product of positive eigenvalues of Gn divided by β, from (4.5)
we have
τ2(n) =
1
β
β−1∏
u=1
sk∏
j=1
|2Tn(wj(u))− 2 cos(
2π u
β
)|. (4.6)
Combining Equations (4.4) and (4.6) we finish the proof of the theorem.
As the first consequence from Theorem 4.1 we have the following result obtained earlier
by Justine Louis [19] in a slightly different form.
Corollary 4.3. The number of spanning trees in the circulant graphs with non-fixed jumps
Cβn(1, α1n, α2n, . . . , αℓn), where 1 ≤ α1 < α2 < . . . < αℓ ≤ [β2 ] is given by the
formula
τ(n) =
n 2β−1
β
β−1∏
u=1
(Tn(1 + 2
ℓ∑
m=1
sin2(
π uαm
β
))− cos(2π u
β
)),
where Tn(w) is the Chebyshev polynomial of the first kind.
Proof. Follows directly from the theorem.
The next corollary is new.
Corollary 4.4. The number of spanning trees in the circulant graphs with non-fixed jumps
Cβn(1, 2, α1n, α2n, . . . , αℓn), where 1 ≤ α1 < α2 < . . . < αℓ ≤ [β2 ] is given by the
formula
τ(n) =
nF 2n
β
β−1∏
u=1
2∏
j=1
|2Tn(wj(u))− 2 cos(
2π u
β
)|,
where Fn is the n-th Fibonacci number, Tn(w) is the Chebyshev polynomial of the first
kind and w1,2(u) =
(
−1±
√
25 + 16
∑ℓ
m=1 sin
2(π uαmβ )
)
/4.
10 Ars Math. Contemp. 23 (2023) #P1.08
We note that nF 2n is the number of spanning trees in the graph Cn(1, 2).
Proof. In this case, k = 2, s1 = 1, s2 = 2 and q = s21 + s
2
2 = 5. Given u we find
wj(u), j = 1, 2 as the roots of the algebraic equation
T1(w) + T2(w) = 2 + 2
ℓ∑
m=1
sin2(
π uαm
β
),
where T1(w) = w and T2(w) = 2w2 − 1. For u = 0 the roots are w1(0) = 1 and w2(0) =
−3/2. Hence, by (4.4), τ1(n) = n5 |2Tn(−
3
2 )−2| =
n
5 |(
−3+
√
5
2 )
n+(−3−
√
5
2 )
n−2| = nF 2n
gives the well-known formula for the number of spanning trees in the graph Cn(1, 2). (See,
for example, [2], Theorem 4). For u > 0 the numbers w1(u) and w2(u) are roots of the
quadratic equation
2w2 + w − 3− 2
ℓ∑
m=1
sin2(
π uαm
β
) = 0.
By (4.6) we get τ2(n) = 1β
∏β−1
u=1
∏2
j=1 |2Tn(wj(u)) − 2 cos(
2π u
β )|. Since τ(n) =
τ1(n)τ2(n), the result follows.
5 Arithmetic properties of the complexity for circulant graphs
It was noted in the series of paper [14, 22, 23, 25] that in many important cases the complex-
ity of graphs is given by the formula τ(n) = p n a(n)2, where a(n) is an integer sequence
and p is a prescribed constant depending only on parity of n.
The aim of the next theorem is to explain this phenomena for circulant graphs with
non-fixed jumps. 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 τ(n) be the number of spanning trees of the circulant graph
Gn = Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn),
where 1 ≤ s1 < s2 < . . . < sk < [βn2 ], 1 ≤ α1 < α2 < . . . , αℓ ≤ [
β
2 ].
Denote by p and q the number of odd elements in the sequences s1, s2, . . . , sk and
α1, α2, . . . , αℓ, respectively. Let r be the square-free part of p and s be the square-free
part of p+ q. Then there exists an integer sequence a(n) such that
10 τ(n) = β n a(n)2, if n and β are odd;
20 τ(n) = β r n a(n)2, if n is even;
30 τ(n) = β sn a(n)2, if n is odd and β is even.
Proof. The number of odd elements in the sequences s1, s2, . . . , sk and α1, α2, . . . , αℓ,
respectively is counted by the formulas p =
∑k
i=1
1−(−1)si
2 and q =
∑ℓ
i=1
1−(−1)αi
2 . We
already know that all non-zero Laplacian eigenvalues of the graph Gn are given by the
formulas λj = L(ζ
j
βn), j = 1, . . . , βn− 1, where ζβn = e
2πi
βn and
L(z) = 2(k + l)−
k∑
i=1
(zsi + z−si)−
ℓ∑
m=1
(znαm + z−nαm).
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 11
We note that λβn−j = L(ζ
βn−j
βn ) = L(ζ
j
βn) = λj .
By the Kirchhoff theorem we have βn τ(n) =
∏βn−1
j=1 λj . Since λβn−j = λj , we
obtain βn τ(n) = (
∏ βn−1
2
j=1 λj)
2 if βn is odd and βn τ(n) = λ βn
2
(
∏ βn
2 −1
j=1 λj)
2 if βn is
even. We note that each algebraic number λj comes into the above products together with
all its Galois conjugate [18]. So, the numbers c(n) =
∏ βn−1
2
j=1 λj and d(n) =
∏ βn
2 −1
j=1 λj
are integers. Also, for even n we have
λ βn
2
= L(−1) = 2(k + l)−
k∑
i=1
((−1)si + (−1)−si)−
ℓ∑
m=1
((−1)nαm + (−1)−nαm)
= 2k −
k∑
i=1
((−1)si + (−1)−si) = 4
k∑
i=1
1− (−1)si
2
= 4p.
If n is odd and β is even, the number βn2 is integer again. Then we obtain
λ βn
2
= L(−1) = 2(k + l)−
k∑
i=1
((−1)si + (−1)−si)−
ℓ∑
m=1
((−1)αm + (−1)−αm)
= 4
k∑
i=1
1− (−1)si
2
+ 4
ℓ∑
m=1
1− (−1)αm
2
= 4p+ 4q.
Therefore, β n τ(n) = c(n)2 if β and n are odd, β n τ(n) = 4p d(n)2 if n is even and
β n τ(n) = 4(p+ q) d(n)2 if n is odd and β is even. Let r be the square-free part of p and
s be the square-free part of p + q. Then there are integers u and v such that p = ru2 and
s = (p+ q)v2. Hence,
1◦
τ(n)
β n
=
(
c(n)
β n
)2
if n and β are odd,
2◦
τ(n)
β n
= r
(
2u d(n)
β n
)2
if n is even and
3◦
τ(n)
β n
= s
(
2 v d(n)
β n
)2
if n is odd and β is even.
Consider an automorphism group Zβn = ⟨g⟩ of the graph Gn generated by the element
g circularly permuting vertices v0, v1, . . . , vβ n−1 by the rule vi → vi+1 and the addition
in the indices is done modulo βn. The action of such a group is uniquely defined on the set
of all edges of Gn, except for those that connect diametrically opposite vertices. Consider
separately two cases αℓ = β/2 and αℓ < β/2.
In the first case, we have two parallel edges between the diametrically opposite vertices
vi and vi+ β n2 , where the indices are taken modβ n. To distinguish them, we orient one of
this edges by the arrow from vi and vi+ β n2 and the other one by the arrow from vi+ β n2 to
vi. As a result, we get exactly β n oriented edges. Denote the edge oriented from vi+ β n2 to
vi by ei and define the action of g on such edges by the rule ei → ei+1, where i is taken
mod β n.
12 Ars Math. Contemp. 23 (2023) #P1.08
In the second case, we have αℓ < β2 and sk <
β n
2 . Therefore, all jumps α1n, . . . , αℓn
and s1, . . . , sk of the graph Gn are strictly less then β n2 and Gn has no edges between the
diametrically opposite edges. That is, the action of group Zβn is well defined on its edges.
So, one can conclude that group Zβn acts fixed point free on the set vertices and on the
set of edges of Gn.
We are aimed to show that it also acts freely on the set of the spanning trees in the
graph. Indeed, suppose that some non-trivial element γ of Zβn leaves a spanning tree A
in the graph Gn invariant. Then γ fixes the center of A. The center of a tree is a vertex
or an edge. The first case is impossible, since γ acts freely on the set of vertices. In the
second case, γ permutes the endpoints of an edge connecting the opposite vertices of Gn.
This means that β n is even, and γ is the unique involution in the group Zβn. This is also
impossible, since the group is acting without fixed edges.
So, the cyclic group Zβn acts on the set of spanning trees of the graph Gn fixed point
free. Therefore τ(n) is a multiple of β n and their quotient τ(n)β n is an integer.
Setting a(n) = c(n)β n in the case 1
◦, a(n) = 2u d(n)β n in the case 2
◦ and a(n) = 2 v d(n)β n
in the case 3◦ we conclude that number a(n) is always integer and the statement of the
theorem follows.
6 Asymptotic for the number of spanning trees
In this section, we give asymptotic formulas for the number of spanning trees for circulant
graphs. It is interesting to compare these results with those in papers [5, 8, 17, 19, 37],
where the similar results were obtained by different methods.
Theorem 6.1. Let gcd(s1, s2, . . . , sk) = d and gcd(α1, α2, . . . , αℓ, β) = 1. Then the
number of spanning trees in the circulant graph
Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn),
1 ≤ s1 < s2 < . . . < sk < [
βn
2
], 1 ≤ α1 < α2 < . . . < αℓ ≤ [
β
2
],
has the following asymptotic
τ(n) ∼ nd
2
β q
An, as n → ∞ and (n, d) = 1,
where q = s21+s
2
2+. . .+s
2
k, A =
∏β−1
u=0 M(Pu) and M(Pu) = exp(
∫ 1
0
log |Pu(e2πit)|dt)
is the Mahler measure of Laurent polynomial
Pu(z) = 2k −
k∑
i=1
(zsi + z−si) + 4
ℓ∑
m=1
sin2(
πuαm
β
).
Proof. By Theorem 4.1, τ(n) = τ1(n)τ2(n), where τ1(n) is the number of spanning trees
in Cn(s1, s2, . . . , sk) and τ2(n) = 1β
∏β−1
u=1
∏sk
j=1 |2Tn(wj(u)) − 2 cos(
2π u
β )|. By ([23],
Theorem 5) we already know that
τ1(n) ∼
nd2
q
An0 , as n → ∞ and (n, d) = 1,
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 13
where A0 is the Mahler measure of Laurent polynomial P0(z). So, we have to find asymp-
totics for τ2(n) only.
By Lemma 3.1, for any integer u, 0 < u < β we obtain Tn(wj(u)) = 12 (zj(u)
n +
zj(u)
−n), where the zj(u) and 1/zj(u) are roots of the polynomial Pu(z) satisfying the
inequality |zj(u)| ≠ 1, j = 1, 2, . . . , sk. Replacing zj(u) by 1/zj(u), if necessary, we can
assume that |zj(u)| > 1 for all j = 1, 2, . . . , sk. Then Tn(wj(u)) ∼ 12zj(u)
n, as n tends
to ∞. So |2Tn(wj(u))− 2 cos( 2π uβ )| ∼ |zj(u)|
n, n → ∞. Hence
sk∏
j=1
|2Tn(wj(u))− 2 cos(
2π u
β
)| ∼
sk∏
s=1
|zj(u)|n =
∏
Pu(z)=0, |z|>1
|z|n = Anu,
where Au =
∏
Pu(z)=0, |z|>1|z| coincides with the Mahler measure of Pu(z). As a result,
τ2(n) =
1
β
β−1∏
u=1
sk∏
j=1
|2Tn(wj(u))− 2 cos(
2π u
β
)| ∼ 1
β
β−1∏
u=1
Anu.
Finally, τ(n) = τ1(n)τ2(n) ∼ nd
2
β q
∏β−1
u=0 A
n
u, as n → ∞ and (n, d) = 1. Since Au =
M(Pu), the result follows.
As an immediate consequence of above theorem we have the following result obtained
earlier in ([8], Theorem 3) by completely different methods.
Corollary 6.2. The thermodynamic limit of the sequence Cβn(s1, s2, . . . , sk,
α1n, α2n, . . . , αℓn) of circulant graphs is equal to the arithmetic mean of small Mahler
measures of Laurent polynomials Pu(z), u = 0, 1, . . . , β − 1. More precisely,
lim
n→∞
log τ(Cβn(s1, s2, . . . , sk, α1n, α2n, . . . , αℓn))
β n
=
1
β
β−1∑
u=0
m(Pu),
where m(Pu) =
∫ 1
0
log |Pu(e2πit)|dt and Pu(z) = 2k −
∑k
i=1(z
si + z−si) +
4
∑ℓ
m=1 sin
2(π uαmβ ).
7 Examples
1. Graph C2n(1, n). (Möbius ladder with double steps). By Theorem 4.1, we have
τ(n) = τ(C2n(1, n)) = n (Tn(3) + 1). Compare this result with ([38], Theorem 4).
Recall [2] that the number of spanninig trees in the Möbius ladder with single steps
is given by the formula n (Tn(2) + 1).
2. Graph C2n(1, 2, n). We have τ(n) = 2nF 2n |Tn(−1−
√
41
4 ) − 1||Tn(
−1+
√
41
4 ) − 1|.
By Theorem 5.1, one can find an integer sequence a(n) such that τ(n) = 2na(n)2
if n is even and τ(n) = na(n)2 if n is odd.
3. Graph C2n(1, 2, 3, n). Here τ(n) = 8n7 (Tn(θ1)−1)(Tn(θ2)−1)
∏3
p=1(Tn(ωp)+1),
where θ1 = −3+
√
−7
4 , θ2 =
−3−
√
−7
4 and ωp, p = 1, 2, 3 are roots of the cubic
equation 2w3 + w2 − w − 3 = 0. We have τ(n) = 6na(n)2 is n is odd and τ(n) =
4na(n)2 is n is even. Also, τ(n) ∼ n28A
n, n → ∞, where A ≈ 42.4038.
14 Ars Math. Contemp. 23 (2023) #P1.08
4. Graph C3n(1, n). We have
τ(n) =
n
3
(2Tn(
5
2
) + 1)2 =
n
3
((
5 +
√
21
2
)n + (
5−
√
21
2
)n + 1)2.
See also ([38], Theorem 5). We note that τ(n) = 3na(n)2, where a(n) satisfies
the recursive relation a(n) = 6a(n − 1) − 6a(n − 2) + a(n − 3) with initial data
a(1) = 2, a(2) = 8, a(3) = 37.
5. Graph C3n(1, 2, n). By Theorem 4.1, we obtain
τ(n) =
n
3
F 2n(2Tn(ω1) + 1)
2(2Tn(ω2) + 1)
2,
where ω1 = −1+
√
37
4 and ω2 =
−1−
√
37
4 . By Theorem 5.1, τ(n) = 3na(n)
2 for
some integer sequence a(n).
6. Graph C6n(1, n, 3n). Now, we get
τ(n) =
n
3
(2Tn(
5
2
) + 1)2(2Tn(
7
2
)− 1)2(Tn(5) + 1).
For a suitable integer sequence a(n), one has τ(n) = 6na(n)2 if n is even and
τ(n) = 18na(n)2 if n is odd.
7. Graph C12n(1, 3n, 4n). In this case
τ(n) =
2n
3
Tn(2)
2(2Tn(
5
2
) + 1)2(Tn(3) + 1)(4Tn(
7
2
)2 − 3)2(2Tn(
9
2
)− 1)2.
By Theorem 5.1, one can conclude that τ(n) = 3na(n)2 if n is even and τ(n) =
6na(n)2 if n is odd, for some sequence a(n) of even numbers.
ORCID iDs
Alexander Mednykh https://orcid.org/0000-0003-3084-1225
Ilya Mednykh https://orcid.org/0000-0001-7682-3917
References
[1] F. T. Boesch and Z. R. Bogdanowicz, The number of spanning trees in a prism, Int. J. Com-
put. Math. 21 (1987), 229–243, doi:10.1080/00207168708803568, https://doi.org/
10.1080/00207168708803568.
[2] F. T. Boesch and H. Prodinger, Spanning tree formulas and Chebyshev polynomials,
Graphs Comb. 2 (1986), 191–200, doi:10.1007/bf01788093, https://doi.org/10.
1007/bf01788093.
[3] D. W. Boyd, Mahler’s measure and invariants of hyperbolic manifolds, in: Number Theory for
the Millennium, I, A K Peters, Natick, MA, pp. 127–143, 2002.
[4] X. Chen, The numbers of spanning trees in undirected circulant graphs, J. Zhangzhou Teach.
Coll., Nat. Sci. 13 (2000), 1–6, http://jxmu.xmu.edu.cn/en/oa/DArticle.
aspx?type=view&id=20060202.
A. Mednykh and I. Mednykh: Complexity of circulant graphs with non-fixed jumps, . . . 15
[5] X. Chen, Q. Lin and F. Zhang, The number of spanning trees in odd valent circulant graphs, Dis-
crete Math. 282 (2004), 69–79, doi:10.1016/j.disc.2003.12.006, https://doi.org/10.
1016/j.disc.2003.12.006.
[6] P. J. Davis, Circulant Matrices, AMS Chelsea Publishing, 1994.
[7] G. Everest and T. Ward, Heights of Polynomials and Entropy in Algebraic Dynamics, Uni-
versitext, Springer-Verlag London, 2013, doi:10.1007/978-1-4471-3898-3, https://doi.
org/10.1007/978-1-4471-3898-3.
[8] M. J. Golin, X. Yong and Y. Zhang, The asymptotic number of spanning trees in circu-
lant graphs, Discrete Math. 310 (2010), 792–803, doi:10.1016/j.disc.2009.09.008, https:
//doi.org/10.1016/j.disc.2009.09.008.
[9] 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, https://doi.
org/10.1088/1751-8113/45/49/494001.
[10] A. J. W. Hilton, Spanning trees and Fibonacci and Lucas numbers, Fibonacci Quart. 12 (1974),
259–262, https://www.fq.math.ca/Scanned/12-3/hilton2.pdf.
[11] J. L. W. V. Jensen, Sur un nouvel et important théorème de la théorie des fonctions,
Acta Math. 22 (1899), 359–364, doi:10.1007/bf02417878, https://doi.org/10.1007/
bf02417878.
[12] P. W. Kasteleyn, Graph theory and crystal physics, in: Graph Theory and Theoretical Physics,
Academic Press, London, pp. 43–110, 1967.
[13] G. R. Kirchhoff, Über die auflösung der gleichungen, auf welche man bei der untersuchung der
linearen verteilung galvanischer ströme geführt wird, Annalen der Physik 148 (1847), 497–508,
doi:10.1002/andp.18471481202, https://doi.org/10.1002/andp.18471481202.
[14] 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, https://doi.org/10.1016/j.
laa.2017.04.032.
[15] D. H. Lehmer, Factorization of certain cyclotomic functions., Ann. Math. (2) 34 (1934), 461–
479, doi:10.2307/1968172, https://doi.org/10.2307/1968172.
[16] R. P. Lewis, The number of spanning trees of a complete multipartite graph, Discrete Math.
197-198 (1999), 537–541, doi:10.1016/s0012-365x(99)90111-5, https://doi.org/10.
1016/s0012-365x(99)90111-5.
[17] M. Li, Z. Chen, X. Ruan and X. Yong, The formulas for the number of spanning trees
in circulant graphs, Discrete Math. 338 (2015), 1883–1906, doi:10.1016/j.disc.2015.04.025,
https://doi.org/10.1016/j.disc.2015.04.025.
[18] D. Lorenzini, Smith normal form and Laplacians, J. Comb. Theory, Ser. B 98 (2008), 1271–
1300, doi:10.1016/j.jctb.2008.02.002, https://doi.org/10.1016/j.jctb.2008.
02.002.
[19] J. Louis, A formula for the number of spanning trees in circulant graphs with non-fixed
generators and discrete tori, Bull. Aust. Math. Soc. 92 (2015), 365–373, doi:10.1017/
s0004972715000969, https://doi.org/10.1017/s0004972715000969.
[20] R. Lyons, Asymptotic enumeration of spanning trees, Comb. Probab. Comput. 14
(2005), 491–522, doi:10.1017/s096354830500684x, https://doi.org/10.1017/
s096354830500684x.
[21] K. Mahler, On some inequalities for polynomials in several variables, J. London Math. Soc. 37
(1962), 341–344, doi:10.1112/jlms/s1-37.1.341, https://doi.org/10.1112/jlms/
s1-37.1.341.
16 Ars Math. Contemp. 23 (2023) #P1.08
[22] A. D. Mednykh and I. A. Mednykh, Asymptotics and arithmetical properties of complexity for
circulant graphs, Dokl. Math. 97 (2018), 147–151, doi:10.1134/s1064562418020138, https:
//doi.org/10.1134/s1064562418020138.
[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, https://doi.org/10.1016/j.disc.2018.08.030.
[24] A. D. Mednykh and I. A. Mednykh, On the structure of the critical group of a circulant
graph with non-constant jumps, Russ. Math. Surv. 75 (2020), 190–192, doi:10.1070/rm9904,
https://doi.org/10.1070/rm9904.
[25] 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,
https://doi.org/10.26493/1855-3974.1355.576.
[26] J. Sedlácěk, On the number of spanning trees of finite graphs, Čas. Pěstovánı́ Mat. 94 (1969),
217–221.
[27] J. Sedlácěk, On the skeletons of a graph or digraph, Combinat. Struct. Appl. (1970), 387–391.
[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, https://doi.
org/10.1088/0305-4470/33/21/303.
[29] D. S. Silver and S. G. Williams, Spanning trees and Mahler measure, 2016,
arXiv:1602.02797v1 [math.CO].
[30] D. S. Silver and S. G. Williams, Graph complexity and Mahler measure, 2017,
arXiv:1701.06097v1 [math.CO].
[31] C. Smyth, The Mahler measure of algebraic numbers: a survey, in: Number Theory and Polyno-
mials, Cambridge University Press, pp. 322–349, 2010, doi:10.1017/cbo9780511721274.021,
https://doi.org/10.1017/cbo9780511721274.021.
[32] 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, https://doi.org/10.11948/
2016006.
[33] F. Y. Wu, Number of spanning trees on a lattice, J. Phys. A: Math. Gen. 10 (1977), L113–115,
doi:10.1088/0305-4470/10/6/004, https://doi.org/10.1088/0305-4470/10/6/
004.
[34] X. Yong and T. Acenjian, The numbers of spanning trees of the cubic cycle c3n and the quadruple
cycle c4n, Discrete Math. 169 (1997), 293–298, doi:10.1016/s0012-365x(96)00092-1, https:
//doi.org/10.1016/s0012-365x(96)00092-1.
[35] F. Zhang and X. Yong, Asymptotic enumeration theorems for the numbers of spanning trees and
Eulerian trails in circulant digraphs and graphs, Sci. China Math., Ser. A 42 (1999), 264–271,
doi:10.1007/bf02879060, https://doi.org/10.1007/bf02879060.
[36] Y. Zhang and M. J. Golin, Further applications of Chebyshev polynomials in the derivation of
spanning tree formulas for circulant graphs, in: Mathematics and Computer Science II. Trends
in Mathematics, Basel: Birkhäuser, pp. 541–553, 2002.
[37] Y. Zhang, X. Yong and M. J. Golin, The number of spanning trees in circulant graphs, Dis-
crete Math. 223 (2000), 337–350, doi:10.1016/s0012-365x(99)00414-8, https://doi.
org/10.1016/s0012-365x(99)00414-8.
[38] 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, https://doi.org/10.1016/j.disc.2004.10.025.