ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 467-485
https://doi.org/10.26493/1855-3974.1355.576
(Also available at http://amc-journal.eu)
On Jacobian group and complexity of the I-graph I(n, k, I) through Chebyshev polynomials
Ilya A. Mednykh *
Sobolev Institute of Mathematics, Koptyuga 4, Novosibirsk, 630090, Russia Novosibirsk State University, Pirogova 1, Novosibirsk, 630090, Russia
4=
Received 21 March 2017, accepted 24 May 2018, published online 26 August 2018
Abstract
We consider a family of I-graphs I(n, k, l), which is a generalization of the class of generalized Petersen graphs. In the present paper, we provide a new method for counting Jacobian group of the I-graph I(n, k,l). We show that the minimum number of generators of Jac(I(n, k, l)) is at least two and at most 2k + 21 - 1. Also, we obtain a closed formula for the number of spanning trees of I(n, k, l) in terms of Chebyshev polynomials. We investigate some arithmetical properties of this number and its asymptotic behaviour.
Keywords: Spanning tree, Jacobian group, I -graph, Petersen graph, Chebyshev polynomial. Math. Subj. Class.: 05C30, 39A10
1 Introduction
The notion of the Jacobian group of a graph, which is also known as the Picard group, the critical group, and the dollar or sandpile group, was independently introduced by many authors ([1, 2,4, 9]). This notion arises as a discrete version of the Jacobian in the classical theory of Riemann surfaces. It also admits a natural interpretation in various areas of physics, coding theory, and financial mathematics. The Jacobian group is an important algebraic invariant of a finite graph. In particular, its order coincides with the number of spanning trees of the graph, which is known for some simplest graphs, such as the wheel,
*The author is grateful to professor D. Lorenzini for helpful comments on the preliminary results of the paper and professor Young Soo Kwon, whose remarks and suggestions assisted greatly in completion of the text. Also, author is thankful to an anonymous referee for valuable recommendations.
The results of this work were partially supported by the Russian Foundation for Basic Research (grants 16-3100138, 18-01-00420 and 18-501-51021) and by the program of fundamental researches of the SB RAS no.I.1.2., project 0314-2016-0007 and the Slovenian-Russian grant (2016-2017).
E-mail address: ilyamednykh@mail.ru (Ilya A. Mednykh)
©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/
468
Ars Math. Contemp. 15 (2018) 441-466
fan, prism, ladder, and Mobius ladder [6], grids [23], lattices [25], prism and anti-prism [26]. At the same time, the structure of the Jacobian is known only in particular cases [4, 7, 9, 17, 20, 21] and [22]. We mention that the number of spanning trees for circulant graphs is expressed is terms of the Chebyshev polynomials; it was found in [8, 27], and [28]. We show that similar results are also true for the I-graph I(n, k, l).
The generalized Petersen graph GP(n, k) has vertex set and edge set given by
V	(GP (n,k)) = {ui,vi | i = 1, 2,...,n}
E (GP (n,k)) = {uiui+i, UiVi, ViVi+k | i = 1, 2,...,n},
where the subscripts are expressed as integers modulo n. The classical Petersen graph is GP(5,2). The family of generalized Petersen graphs is a subset of so-called I-graphs ([3, 14]). The I-graph I(n, k, l) is a graph of the following structure
V	(I (n,k,l)) = {ui,vi | i = 1, 2,...,n}
E(I(n,k,l)) = {uiui+i, UiVi, ViVi+k | i = 1, 2, .. . ,n}.
where all subscripts are given modulo n.
Since I(n, k, l) = I(n, l, k) we will usually assume that k < l. In this paper we will deal with 3-valent graphs only. This means that in the case of even n and l = n/2 the graph under consideration has multiple edges. The graph I(n, l, k) is connected if and only if gcd(n, k,l) = 1. If gcd(n, k,l) = m > 1, then I(n, k, l) is a union of m copies of the graph I(n/m, k/m,l/m). If m = 1 and gcd(k, l) = d, then the graphs I(n, k, l) and I(n,k/d,l/d) are isomorphic [5, 16, 24]. In the case of l = 1 it easy to see that the graph I(n, k, 1) coincides with the generalized Petersen graph GP(n, k). The number of spanning trees and the structure of Jacobian group for the generalized Petersen graph were investigated in [19]. The spectrum of the I-graph was found in [11]. Even though the number of spanning trees of a given graph can be computed through eigenvalues of its Laplacian matrix, it is not easy to find the number of spanning trees for I(n, k, l) using them. In this paper, we obtained a closed formula for the number of spanning trees for I(n, k, l), investigate some arithmetical properties of this number and provide its asymptotic behavior. Also, we suggest an effective way for calculating Jacobian of I(n, k, l) and find sharp upper and lower bounds for the rank of Jac(I(n, k,l)).
2 Basic definitions and preliminary facts
Consider a connected finite graph G, allowed to have multiple edges but without loops. We endow each edge of G with the two possible directions. Since G has no loops, this operation is well defined. Let O = O(G) be the set of directed edges of G. Given e e O(G), we denote its initial and terminal vertices by s(e) and t(e), respectively. Recall that a closed directed path in G is a sequence of directed edges e-i e O(G), i = 1,... ,n such that t(ei) = s(ei+1) for i = 1,... ,n - 1 and t(en) = s(e^).
Following [1] and [2], the Jacobian group, or simply Jacobian Jac(G) of a graph G is defined as the (maximal) Abelian group generated by flows u(e), e e O(G), obeying the following two Kirchhoff laws:
Ki. the flow through each vertex of G vanishes, that is J2eeo t(e)=x ^(e) = 0 for all
x e V(G);	'
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
469
K2: the flow along each closed directed path W in G vanishes, that is J2eew w(e) = 0.
Equivalent definitions of the group Jac(G) can be found in papers [1, 2, 4, 9, 12, 18, 20].
We denote the vertex and edge set of G by V(G) and E(G), respectively. Given u, v e 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,veV(G), called the adjacency matrix of the graph G. The degree d(v) of a vertex v e V(G) is defined by d(v) = J2u auv. Let D = D(G) be the diagonal matrix indexed by the elements of V(G) with dvv = d(v). Matrix L = L(G) = D(G) - A(G) is called the Laplacian matrix, or simply Laplacian, of the graph G.
Recall [20] the following useful relation between the structure of the Laplacian matrix and the Jacobian of a graph G. Consider the Laplacian L(G) as a homomorphism Z|V 1 ^ Z|V|, where |V| = |V(G)| is the number of vertices in G. The cokernel coker(L(G)) = Z|V 1 / im(L(G)) — is an Abelian group. Let
coker(L(G)) = Zdl 0 Zd2 © • • • © Zd|V| be its Smith normal form satisfying the conditions dj |di+1, (1 < i < | V|). If the graph is
connected, then the groups Zdl, Zd2
— are finite, and \
IV |
Z. In this case,
Jac(G) = Zt1 © Zt2 © • • • © Zd
IV |-1
is the Jacobian of the graph G. In other words, Jac(G) is isomorphic to the torsion subgroup of the cokernel coker(L(G)).
Let M be an integer n x n matrix, then we can interpret M as a homomorphism from Zn to Zn. In this interpretation M has a kernel ker M, an image im M, and a cokernel coker M = Zn/ im M. We emphasize that coker M of the matrix M is completely determined by its Smith normal form.
In what follows, by In we denote the identity matrix of order n.
We call an n x n matrix circulant, and denote it by circ(a0, a1,..., an-1) if it is of the form
/
circ(ao, ai, .. ., a„_i)
«0
ai a2
«n-1 «o «1
ai
a2 a3
an-1
a^ 2
ao J
Recall [10] that the eigenvalues of matrix C = circ(a0, a^ ..., an-1) are given by the following simple formulas Xj = p(en), j = 0,1,..., n -1 where p(x) = a0 + a1x + • • • + an-1xn-1 and e„ is the order n primitive root of the unity. Moreover, the circulant matrix C = p(T), where T = circ(0,1,0,..., 0) is the matrix representation of the shift operator T: (xo, X1,... ,x„_2, xn_1 ) ^ (x1,x2,..., x„_1 ,xo).
By [15, Lemma 2.1] the 2n x 2n adjacency matrix of the I-graph I(n, k, l) has the following block form
A(1 (n,k,1))
In
cn
where CÎ is the n x n circulant matrix of the form
Ck = circ(0,..., 0,1, 0,..., 0,1,0,..., 0).
k times
i-2fc-1
k — 1 times
V1
k
n
n
470
Ars Math. Contemp. 15 (2018) 441-466
Denote by L = L(I(n, k, l)) the Laplacian of I(n, k, l). Since the graph I(n, k, l) is three-valent, we have
L = 3I2n - A(I(n, k, l)) = (3I"_- ^^ 3 3 Cokernels of linear operators
Let P(z) be a bimonic integer Laurent polynomial. That is P(z) = zp + aizp+1 + • • • + as-1zp+s-1 + zp+s for some integers p, a1, a2,..., as-1 and some positive integer s. Introduce the following companion matrix A for the polynomial P(z):
0 I Is_ 1 '
.4 =
-1, — «1,. .., —a.
s — 1
where Is—1 is the identity (s - 1) x (s - 1) matrix. We will use the following properties of A. Note that det A = (-1)s. Hence A is invertible and inverse matrix A—1 is also integer matrix. The characteristic polynomial of A coincides with z—pP(z).
Let A = (ay, j G Z) be a free Abelian group freely generated by elements ay, j G Z. Each element of A is a linear combination J2 j cj aj with integer coefficients cy.
Define the shift operator T: A ^ A as a Z-linear operator acting on generators of A by the rule T: ay ^ aj+1, j G Z. Then T is an endomorphism of A. Let P(z) be an arbitrary Laurent polynomial with integer coefficients, then A = P (T) is also an endomorphism of A. Since A is a linear combination of powers of T, the action of A on generators ay can be given by the infinite set of linear transformations A: ay ^ J2i ai,ja, j € Z. Here all sums under consideration are finite. We set ftj = J2i ai,jai. Then im A is a subgroup of A generated by ftj, j G Z. Hence, coker A = A/ im A is an abstract Abelian group (xi, i G Z | J2i ai,jxi = 0, j G Z) generated by xi, i G Z with the set of defining relations J2i ai,jxi =0, j G Z. Here Xj are images of a.j under the canonical homomorphism A ^ A/ im A. Since T and A = P(T) commute, subgroup im A is invariant under the action of T. Hence, the actions of T and A are well defined on the factor group A/ im A and are given by T: Xj ^ xj+1 and A: Xj i ai,jxi respectively.
This allows to present the group A/ im A as follows (xi, i G Z | P(T)xj = 0, j G Z). In a similar way, given a set P1(z), P2(z),..., Ps(z) of Laurent polynomials with integer coefficients, one can define the group (xi, i G Z | P^T)xj = 0, P2(T)xj = 0,...,Ps(T)xj =0, j G Z).
We will use the following lemma.
Lemma 3.1. Let T: A ^ A be the shift operator. Consider endomorphisms A and B of the group A given by the formulas A = P(T), B = Q(T), where P(z) and Q(z) are Laurent polynomials with integer coefficients. Then B: A ^ A induces an endomorphism B coker a of the group coker A — A/ im A defined by B|coker A(a + im A) — B(a)+im A, a G A. Furthermore
(xi, i G Z | A(T)xj = 0, B(T)xj = 0, j G Z) =
coker A/ im(B|coker a) = coker(B|TOker a).
Proof. The images im A and im B are subgroups in A. Denote by (im A, im B) the subgroup generated by elements of im A and im B. Since P(z) and Q(z) are Laurent polynomials, the operators A = P(T) and B = Q(T) do commute. Hence, subgroup im A
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
471
is invariant under endomorphism B. Indeed for any y = Ax G im A, we have By = B(Ax) = A(Bx) G im A. This means that B: A ^ A induces an endomorphism of the group coker A = A/ im A. We denote this endomorphism by B|coker A. We note that the Abelian group (xj, i G Z | A(T)xj = 0, B(T)xj = 0, j G Z) is naturally isomorphic to A/ (im A, im B). So we have
A/ (im A, im B) = (A/ im A)/im(B|coker a) =
coker A/ im(B|TOker a) = coker(B|coker a).
The lemma is proved.	□
4 Jacobian group for the /-graph I(n, k, l)
In this section we prove one of the main results of the paper. We start in the following theorem.
Theorem 4.1. Let L = L(I(n, k, l)) be the Laplacian of a connected I-graph I(n, k, l). Then
coker L = coker(An — I), where A is 2(k + l) x 2(k + l) companion matrix for the Laurent polynomial
(3 — zk — z—k )(3 — zl — z—l) — 1.
Proof. Let L be the Laplacian matrix of the graph I(n, k, l). Then, as it was mentioned above, L is a 2n x 2n matrix of the form
L _ Z' 3In Cn	^n
V —^n	3In — Ch
where Ck = circ(0,..., 0,1,0,..., 0,1,0,..., 0).
k times	k — 1 times
Consider L as a Z—linear operator L: Z2n ^ Z2n. In this case, coker(L) is an abstract Abelian group generated by elements x1, x2,..., xn, y1, y2,..., yn satisfying the system of linear equations 3xj — xj—k — xj+k — yj = 0, 3yj — yj—l — yj+1 — xj =0 for any j = 1,..., n. Here the indices are considered modulo n. By the property mentioned in Section 2, the Jacobian of the graph I(n, k, l) is isomorphic to the finite part of cokernel of the operator L.
To study the structure of coker(L) we extend the list of generators to the two bi-infinite sequences of elements (xj jeZ and (yj )jeZ setting xj+mn = xj and yj+mn = yj for any m G Z. Then we have the following representation for cokernel of L:
coker(L) = (xj, yj, i G Z | 3xj — xj+k — xj—k — yj = 0,
3yj — yj+i — yj—i — xj = 0,xj+n = xj ,yj+n = yj, j g Z).
Let T be the shift operator defined by the rule T: xj ^ xj+1, yj ^ yj+1, j G Z. Consider the operator P(T) defined by P(T) = (3 — Tk — T—k)(3 — T1 — T—l) — 1. We
472
Ars Math. Contemp. 15 (2018) 441-466
use the operator notation from Section 3 to represent the cokernel of L. Then we have
coker(L) = (x,, y,, i e Z | (3 - Tk - T-k)xcj = , (3 - T1 - T= x^-, Tnxj = xj, Tnyj = yj ,j e Z> = (x,, i e Z | (3 - T1 - T-1 )(3 - Tk - T-k^ = x^-,Tnxj = x^-, j e Z> = (x,, i e Z | ((3 - Tk - T-k)(3 - T1 - T-1) - 1)xj = 0,
(Tn - 1)xj = 0, j e Z> = (x,, i e Z | P(T)xj = 0, (Tn - 1)xj = 0, j e Z>.
To finish the proof, we apply Lemma 3.1 to the operators A = P(T) and B = Q(T) =
Tn - 1.
Since the Laurent polynomial P(z) = (3 - zk - z-k)(3 - z1 - z-1) - 1 is bimonic, it can be represented in the form P(z) = z-k-1 + aiz-k-1+1 + • • • + a2k+21-1zk+1-1 + zk+1, where a1, a2,..., a2k+21-1 are integers. Then the corresponding companion matrix A is
(_0 | l2k+21-1_A
y -1, -«1,..., -a2k+2i-1 J
It is easy to see that det A =1 and its inverse A-1 is also integer matrix. For convenience we set s = 2k + 21 to be the size of matrix A. Note that for any j e Z the relations P(T)xj = 0 can be rewritten as xj+s = - xj - a1xj-+1 - • • • - as-1xj+s-1. Let xj = (xj+1, xj+2,..., xj+s)4 be s-tuple of generators xj+1, xj+2,..., xj+s. Then the relation P(T)xj = 0 is equivalent to xj = Axj-1. Hence, we have x1 = Ax0 and x-1 = A-1 x0, where x0 = (x1, x2,..., xs)'. So, xj = Aj x0 for any j e Z. Conversely, the latter implies xj = A xj-1 and, as a consequence, P(T)xj = 0 for all j e Z.
Consider coker A = A/ im A as an abstract Abelian group with the following representation (x,, i e Z | P(T)xj = 0, j e Z>.
Our present aim is to show that coker A = Zs. We have
coker A = (x,, i e Z | P(T^ = 0, j e Z>
= (xj, j e Z | x£ + 01x^+1 +-----+ as-1x£+s-1 + x£+s = 0, i e Z>
= (xj, j e Z | (x^+1, x£+2,..., x^+s)4 = A(x£,x£+1,..., x^+s—1)4, i e Z> = (xj, j e Z | (x^+1, x^+2,..., x^+s)4 = A£(x1, x2,..., xs)4,i e Z> = (x1,x2,...,xs | 0> = Zs.
Now we describe the action of the endomorphism B|coker A on the coker A. Since the operators A = P(T) and T commute, the action T|coker A: xj ^ xj+1, j e Z on the coker A is well defined. First of all, we describe the action of T |coker A on the set of generators x1, x2,..., xs. For any i = 1,..., s - 1, we have T|coker(x,) = x,+1 and T|coker a(xs) = xs+1 = -x1 - 01x2 - • • • - 0s-2xs-1 - as-A. Hence, the action of T |coker A on the coker A is given by the matrix A. Considering A as an endomorphism of the coker A, we can write T | coker a = A. Finally, B| coker a = Q(T | coker a ) = Q(A). Applying Lemma 3.1, we finish the proof of the theorem.	□
Corollary 4.2. The Jacobian group Jac(I(n, k, 1)) of a connected I-graph I(n, k, 1) is isomorphic to the torsion subgroup of coker(An - I), where A is the companion matrix for the Laurent polynomial (3 - zk - z-k )(3 - z1 - z-1) - 1.
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
473
The Corollary 4.2 gives a simple way to find Jacobian group Jac(I (n, k, /)) for small values of k, / and sufficiently large numbers n. The numerical results are given in the Tables 2 and 3.
5 Counting the number of spanning trees for the I-graph I(n, k, l)
In what follows, we always assume that the numbers k and / are relatively prime. To get the result for an arbitrary connected I-graph I(n, k, /) with gcd(n, k, /) = 1 and gcd(k, /) = d > 1 we observe that I(n, k, /) is isomorphic to I(n, k', /'), where the numbers k' = k/d and /' = //d are relatively prime.
Theorem 5.1. The number of spanning trees of the I-graph I(n, k, /) is given by the formula
k+l-1 ,
k + l 1 rp ( \ -i
Tk,i(n) = ( —1)(n-1)(k+l)n n T"(Ws) - 1,
s = 1 W - 1
where ws, s = 1,2,..., k + l — 1 are roots of the order k + l — 1 algebraic equation
(3 - 2Tk(w))(3 - 2Ti(w)) - 1 =Q w — 1
and Tj (w) is the Chebyshev polynomial of the first kind.
Proof. By the celebrated Kirchhoff theorem, the number of spanning trees rk}i (n) is equal to the product of nonzero eigenvalues of the Laplacian of a graph I(n, k, l) divided by the number of its vertices 2n. To investigate the spectrum of Laplacian matrix we note that matrix C% = Tk + T-k, where T — circ(0,1,..., 0) is the n x n shift operator. The latter equality easily follows from the identity Tn = In. Hence,
L = f3In — Tk — T-k	—In
^ = '	In	^
n
The eigenvalues of circulant matrix T are en, where en = e ~. Since all eigenvalues of T are distinct, the matrix T is conjugate to the diagonal matrix T = diag(1, en,..., e;-1), where diagonal entries of diag(1, en,..., e;-1) are 1, en,..., e;-1. To find spectrum of L, without loss of generality, one can assume that T = T. Then the blocks of L are diagonal matrices. This essentially simplifies the problem of finding eigenvalues of L. Indeed, let A be an eigenvalue of L and (x, y) = (x1,..., xn, y1,..., yn) be the corresponding eigenvector. Then we have the following system of equations
( (3In - Tk - T-k)x - y = Ax \-x + (3In - Tl - T-l)y = Ay .
From here we conclude that y = (3In - Tk - T-k)x - Ax = ((3 - A)In - Tk - T-k)x. Substituting y in the second equation, we have (((3 - A)I„ - Tl - T-l)((3 - A)I„ - Tk -
T-k) - 1)x = 0.
Recall the matrices under consideration are diagonal and the (j +1, j + 1)-th entry of T is equal to en. Therefore, we have ((3 - A - enk - e-jk )(3 - A - e;1 - e-jl) - 1)xj-+1 = 0 and yj+1 = (3 - A - e;1 - e-jl
474
Ars Math. Contemp. 15 (2018) 441-466
So, for any j = 0,..., n - 1 the matrix L has two eigenvalues, say Aij and A2 j satisfying the quadratic equation (3 - A - enk - e—jk)(3 - A - enl - e—jl) - 1 = 0. The corresponding eigenvectors are (x, y), where
x = ej+1 = (0,...,	,..., 0) and
(j+1)-th
y =(3 - A - Tk - T—k)ej+i.
In particular, if j =0 for A1j0, A2,0 we have (1 - A)(1 - A) - 1 = A(A - 2) = 0. That is, A1j0 = 0 and A2,0 = 2. Since A1 j and A2j are roots of the same quadratic equation, we obtain Aid A-j = P (en), where P (z) = (3 - zk - z—k )(3 - zl - z—l) - 1. Now we have
n—1	n—1	n—1
2nA2,o n A1,j A2,j=n n A1,j A2,j=n np (en: j=1 j=1 j=1
To continue we need the following lemma. Lemma 5.2. The following identity holds
(3 - zk - z—k)(3 - zl - z—l) - 1 = (3 - 2Tk(w))(3 - 2Tl(w)) - 1,
where Tk (w) is the Chebyshev polynomial of the first kind and w = -1- (z + z—1). Moreover, if k and l are relatively prime then all roots of the Laurent polynomial
(3 - zk - z—k)(3 - zl - z—l) - 1
counted with multiplicities are 1, 1, z1, 1/z1,..., zk+l—1, 1/zk+l—1, where we have |zs | = 1, s = 1, 2,..., k + l - 1. So, the right-hand polynomial has the roots 1, w1, ..., wk+l—1, where ws = 1 for all s = 1, 2,..., k + l - 1.
Proof. Let us substitute z = e®v. It is easy to see that w = - (z + z—1) = cos y>, so we have Tk (w) = cos(k arccos w) = cos(k^). Then the first statement of the lemma is equivalent to the following trigonometric identity
(3 - 2cos(ky))(3 - 2cos(ly)) - 1 = (3 - 2Tk(w))(3 - 2Tl(w)) - 1.
To prove the second statement of the lemma we suppose that the Laurent polynomial
P(z) = (3 - zk - z—k)(3 - zl - z—l) - 1 has a root zo such that |zo| = 1. Then zo = eiV0, (o e R. Now we have (3 - 2cos(k(o))(3 - 2cos(lyo)) - 1 = 0. Since 3 - 2 cos(k(0) > 1 and 3 - 2 cos(ly0) > 1 the equations holds if and only if cos(k(0) = 1 and cos(l(0) = 1. So ky0 = 2ns0 and ly0 = 2nt0 for some integer s0 and t0. As k and l are relatively prime, so there exist two integers p and q such that kp + ql = 1. Hence = (0(kp + lq) = 2n(ps0 + qt0) e 2nZ. As a result z0 = e®V0 = 1. Now we have to show that the multiplicity of the root z0 = 1 is 2. Indeed, P(1) = P'(1) = 0 and P"(1) = -2(k2 + l2) = 0.	□
Let us set H(z) = f]s=1(z - zs)(z - zs 1), where m = k + l - 1 and zs are roots of P(z) different from 1. Then by Lemma 5.2, we have P(z) = (zk+) H(z).
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
475
Lemma 5.3. Let H(z) = f]m=i(z - zs)(z - zs ") and H(1) = 0. Then
n—1	m rp , , 1
n h (,i)=n ,
j=1	s=1 s
where ws = ^ (zs + z-1), s = 1,..., m and T" (x) is the Chebyshev polynomial of the first kind.
Proof. It is easy to check that "—/(z - en) = 11 if z = 1. Also we note that 1 (zn + z-n) = Tn( 1 (z + z-1)). By the substitution z = e®the latter follows from the evident identity cos(ny) = T"(cos y). Then we have
n—1	n—1 m
n H(e")= nn(en - z,)(e" - z—1)
j=1	j=1 s = 1
m n- 1
= nn (zs - e")(zs-1 - e")
s = 1 j=1
= n z" - 1 z—" - 1 = m Tn(ws) - 1
J=1 zs - 1 z—1 - 1 J=1 ws - 1 .
Note that nnua - ) = limnnL!(z - j = lim Z-T = n and n^! j
(- 1)n- 1. As a result, taking into account Lemma 5.2 and Lemma 5.3, we obtain
1 n-1 1 n-1 (ej - 1)2 Tk,i(n) = n n P (en) = n n j+rH (£n) j=1 j=1
2 n-1
n ^ ' n ^ (en)k+1
^-- II H(en)
j=1
k + 1 — 1 rrt / N -|
(-1)(n-1)(fc+i)n TT Tn(Ws) - 1.	□
S = 1 W - 1
IS" Un-1 xMW
2
where ws, s = 1, 2,..., k are
Corollary 5.4. rfc,;(n) = n f]s+1 U„
the same as in Theorem 5.1 and Un—1(w) is the Chebyshev polynomial of the second kind.
Proof. Follows from the identity ''—1 = U"—1 (y'^+p ) .	□
The following theorem appeared after fruitful discussion with professor D. Lorenzini.
Theorem 5.5. Let t (n) = rk,; (n) be the number of spanning trees of the graph I (n, k, l). Then there exist an integer sequence a(n) = ak,; (n), n G N such that
1° t(n) = n a2(n) when n is odd,
2° t(n) = 6n a2(n) when n is even and k + l is even,
3° t(n) = n a2(n) when n is even and k + l is odd.
476
Ars Math. Contemp. 15 (2018) 441-466
Proof. Recall that all nonzero eigenvalues are given by the list |A2,o, A^j, A2,j, j = 1,..., n — 1}. By the Kirchhoff theorem we have 2nr(n) = A2,0 n^-i A1,jA2,j.
Since A2 0 = 2, we have nr(n) = f]A1,jA2,j. We note that A1,jA2,j = P(en) = P(en-j) = A1,n-jA2,n-j. So, we get nr(n) = (nj=-1)/2 A1,jA2,j)2 if n is odd and nr(n) = A1,n A2,n (nn=1-1 A1,jA2,j)2, if n is even. The value A1,nA2,n = P( —1) = (3 — 2( —1)k)(3 — 2( —1)1) — 1 is equal to 4 if k and l are of different parity and 24 if both k and l are odd. The case when both k and l are even is impossible, since k and l are relatively prime.
The graph I(n, k, l) admits a cyclic group of automorphisms isomorphic to Zn which acts freely on the set of spanning trees. Therefore, the value t(n) is a multiple of n. So is an integer. Hence
/ \ t of"-1)/2 A A x 2
I 0 t(n) = [ 11, = 1 A1,jA2,j n
when n is odd,
20 T(n) = 6 ( 2 n Al,j A2,j ) when n is even and k + l is even,
n/ 2 -1	2
30 ^ = ( 2°A1,jX2,j\ when n is even and k + l is odd.
nn
Each algebraic number A^ comes into both products n(=-1)/2 A1,j A2 j and
j-1 A1,j A2,j with all its Galois conjugate elements. Therefore, both products are integer numbers. From here we conclude that in equalities 10, 20 and 30 the value that is squared is a rational number. Because T(n) is integer and 6 is a squarefree, all these
rational numbers are integer. Setting a(n) = —n—j—~ if n is odd and a(n) =
if n is even, we finish the proof of the theorem.	□
2HI ?=1-1 A1,j A
From now on, we aim to estimate the minimum number of generators for the Jacobian of I-graph I(n, k, l).
Lemma 5.6. For any given I-graph I(n, k, l) the number of spanning trees t (n) satisfies the inequality t(n) > n3.
Proof. Recall that for any j = 0,..., n — 1, the Laplacian matrix L of I(n, k, l) has two eigenvalues, say A1 j and A2 j, which are roots of the quadratic equation Q (A) = (3 — A —
enk —e-jk)(3—A—en1 —e-j1) —1 = 0. So, AuA2,j = (3—enk —e-jk)(3— e^ — e-j1) — 1 = P (en). Note that A1,0 = 0 and A2,0 = 2. Furthermore {A1,j, A2,j | j = 0,..., n — 1} is the set of all eigenvalues of L. The Kirchhoff theorem states the following
n- 1	n- 1
,0
2nTfc,;(n) = 2nT(n) = A2,o JJ A1,jA2,j = 2 JJ A1,jA2,j.
j=1 j=1
Hence nT (n) = ¿1 P (en), where P (en) = (3 — 2cos( ))(3 — 2cos( j-)) — 1.
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
477
It is easy to prove the following trigonometric identity
3 - 2cos ( j^)) (3 - 2cos (j^)) - 1 =
4sin2 f—) + 4sin2 (—) + 16 sin2 (—) sin2 (—) . V n J	V n J	V n J V n J
Connectedness of I-graph implies gcd(n, k,l) = 1. It may happen that gcd(n, k) m = 1 and gcd(n, l) = m' =1. We will use the notation n = m q = m'q', k = p m, l p'm'. We introduce three sets, J, Jk and J; in the following way
J = {1, 2,..., n - 1}, Jk = {j | j = dq, d = 1,..., m - 1} and J; = {j | j = d' q', d' = 1,..., m' - 1}.
If j G Jfc then sin( ^ ) = 0 and if j G J| then sin( ) =0. We note that Jk and J do not intersect. Otherwise, for j G Jk n J; we have A1 j A2 j = P (en) = 0. Then at least one of the eigenvalues A1 j and A2 j is equal to zero. This leads to contradiction, as we have the unique zero eigenvalue A1j0 = 0. Now we are going to find a low bound for r(n). As
nr (n) = f]"—j1 P (en) we evaluate the product
n-1
ij=i J vcn
n-1
np(en)=n 4si
sin2 ( j—j +4 sin
2 jn) +i6sin2 jn) sin2 ( ^)
V n /	V n / Vn/
> n 4sin2 ( j^) n 4sin2 ( ^) n ^ (^) s^ (jin)
jeJk
jeJi
je J\(JfcUJi)
sin - sin . .
nn
n 4s,n= ^) n 4^ (ç).
jeJ\Jk
jeJ \Ji
n
Now we analyze individual component of the product. We make use of the following simple identity cos(2jpn) = cos(2(j+q)pn).
n 4 sin2 (jf ) = n(2 - 2
jeJ\Jk	jeJ\Jk
cos (^)) = n (2 - 2cos ^
jeJ\Jk
n (2 - 2«
jeJ \Jk
n
( 2jpn ) v q
q-1
) =11 2 - 2
j=1
f2jmpK\
- 2 cos (-
mq /
2jpn
q

The Chebyshev polynomial Tq(x) = cos(q arccos(x)) has the following property. The roots of the equation Tq(x) - 1=0 are cos( j), j = 0,1,..., q - 1. Since the leading coefficient of Tq(x) is 2q-1, for x =1 we have the identity
q-1
j=1
n(2x - 2cos(j
t,(x) - 1
x1
478
Ars Math. Contemp. 15 (2018) 441-466
As p and q are relatively prime we obtain
q-1
n (2 - 2 cos j=i
2jpn
q-1
n
2 2 cos
2>X
q ^
Hence
^Q 4 sin
je J
In a similar way we obtain
lim
2 (?)
T(x) - 1 x — 1
/ n \ 2m
\mJ
(q2)
,2\ m
m
2m
n 4 sin 2 ( ^ ) = ( n -LJ-	V n / Vm'
jeJ \Ji
2m'
To get the final result we use the following trivial inequality. For any integers a > 2 and b > 2 we have ab > ab. Since q = n/m > 2 and q' = n/m' > 2, we conclude
a-1
2m n 2
j=1
» = 11P(j) > (n)( m
> n2 n2 = n4.
□
Using Lemma 5.6, one can show the following theorem.
Theorem 5.7. For any given I-graph I(n, k, /) the minimum number of generators for Jacobian Jac(I(n, k, /)) is at least 2 and at most 2k + 2/ — 1.
Proof. The upper bound for the number of generators follows from Theorem 4.1. Indeed, by this theorem the group coker(L(I(n, k, /)) = Jac(I(n, k, /)) © Z is generated by 2k + 2/ elements. One of these generators is needed to generate the infinite cyclic group Z. Hence Jac(I(n, k, /)) is generated by 2k + 2/ — 1 elements.
To get the lower bound we use Lemma 5.6. Let us suppose that Jac(I(n, k, /)) is generated by one element. Then it is the cyclic group of order t (n). Denote by D be a product of all distinct nonzero eigenvalues of I(n, k, /). By Proposition 2.6 from [20] the order of each element of Jac(I(n, k, /)) is divisor of D. Hence, t(n) is divisor of D and we have inequality D > t (n). By the Kirchhoff theorem we have 2nT (n) = A2,0 rj—i A1 A2j. We note that all algebraic numbers Ai}j comes into product together with its Galois conjugate, so 2nT (n) is a multiple of D. In particular 2nT (n) > D.
_ fn("-l)/2
From the proof of Theorem 5.5 we have nT(n) =
j=i
A2,j)2 if n is odd
and nr(n) = A1,n A2,n (rij=i-1 A^jA2,j)2 if n is even. Moreover, the value A1,nA2,n is equal to 4 if k and l are of different parity and 24 if both k and l are odd. The case when both k and l are even is impossible as k and l are relatively prime.
Now, we have 4nr(n) = (^nj=-1)/2 A1,jA2j-)2 if n is odd. Again, all algebraic
numbers Ajj comes into the product p = 2\\j=-1)/2 A1,j A2j together with its Galois conjugate. Therefore, the product p is an integer number and contains all distinct nonzero eigenvalues. Hence p is a multiple of D. So we obtain 4nr(n) = p2 > D2 > t(n)2.
m
m
q
m
m
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
479
Also we get 4nAi,n A2,n t(n) = (2Ai,n A2,n n"=1-1 A2,j)2 if n is even. By a similar argument, taking into account the inequality 24 > A1; n A2, n we obtain 96nT(n) > 4nA1,nA2,nt(n) > D2 > t(n)2.
As result, by Lemma 5.6 we have 4n > t(n) > n3 if n is odd and 96n > t(n) > n3 if n is even. For n > 10 this is impossible. So, the rank of Jac(1 (n, k, 1)) is at least two for all n > 10. For n less than 10 this statement can be proved by direct calculation.	□
For graphs I(4,2, 3) and I(6, 3,4), the Jacobian group Jac(1 (n, k, 1)) is generated by 2 elements. The upper bound 2k + 21 — 1 for the minimum number of generators of Jac(1 (n, k, 1)) is attained for graph I(34, 2,3) and I(170,3,4). See Tables 2 and 3 in Section 7.
So the lower bound 2 and the upper bound 2k + 21 — 1 for the minimum number of generators of Jac(1 (n, k, 1)) are sharp.
6 Asymptotic for the number of spanning trees
The asymptotic for the number of spanning trees of the graph I(n, k, 1) is given in the following theorem.
Theorem 6.1. Let P(z) = (3 — zk — z-k)(3 — z1 — z-1) — 1. Suppose that k and 1 are relatively prime and set = n P O)=o |z|>1 | z |. Then the number Tk,;(n) of spanning trees of the graph I(n, k, 1) has the asymptotic
TM(n) ~	AM, n
Proof. By Theorem 5.1 we have
k + 1 rp / \ -i
Tfc,i(n) = ( — 1)("-1)(k+0n n T"(Ws) — 1,
J=1 Ws — 1
where ws, s = 1, 2,...,k + 1 — 1 are roots of the polynomial
Q( ) (3 — 2Tk(w))(3 — 2Ti(w)) — 1
Q(w) =-;-.
w — 1
So we obtain
fc+i-1
fc+i-1 ,fc+i-1
Tfc,i(n) = n	T"wWWs_) 1 1 = n	|T„(ws) — 1| /	|ws — 1|.
s=1	s	s = 1	' s=1
By Lemma 5.2 we have T"(ws) = 2(z" + z-"), where the zs and 1/zs are roots of the polynomial P(z) with the property |zs | = 1, s = 1, 2,..., k + 1 — 1. Replacing zs by 1/zs, if it is necessary, we can assume that all |zs| > 1 for all s = 1, 2,..., k +1 — 1. Then
T"(ws) — 1 z" as n tends to to. So |T"(ws) — 1| — 2>|zs|" as n ^ to. Hence
fc+i-1 1 fc+i-1 1 1
1	1 1	1	11	1	1	4"
n |T"(ws)—1| - ^ro n |zs|"=^¡^11 |z|"=^fc+T-ra
s=1	s=1	P(z) = 0, |z|>1
480
Ars Math. Contemp. 15 (2018) 441-466
Now we directly evaluate the quantity f] k=1 1 |ws - 11. We note that
Q(w) = aowk+i-1 + aiwk+l-2 +-----+ ak+i-2w + afc+i-1
is an integer polynomial with the leading coefficient a0 = 2k+i. From here we obtain
k+i-1 k+i-1
n iws - ii = n ii -wsi
aL Q(i) a0
2(k2 + l2) k2 + l2
2 k+l 2k+1-1 '
s=1	s=1
Indeed,
Q	= lim (3 - 2Tk(w))(3 - 2T1(w)) - 1
w — 1
= -2Tk(1)(3 - 2Ti(1)) - 2T/(1)(3 - 2Tk(1)) = -2kUk-1(1)(3 - 2Ti(1)) - 21U-1(1)(3 - 2Tk(1)) = -2(k2 + l2)
and a0 = 2k+l.
In order to get the statement of the theorem we combine the above mentioned results. Then
Af,i / k2 + l2 n
f \	Ak,i Ik2 +12	n
Tk,i(n) ~ n 2+1-1/	= klTp Ak,i as n ^
□
Remark 6.2. It was noted by professor A. Yu. Vesnin that constant Ak l coincides with the Mahler measure of Laurent polynomial P (z) = (3 - zk - z-k )(3 - zl - z-1) - 1. It gives a simple way to evaluate Ak l using the following formula
Ak,i =exp(^1 log IP(e2nii)|d^.
See, for example, [13, p. 6] for the proof.
The numerical values for Ak i, where k and 1 are relatively prime numbers 1 < k < 1 < 9 will be given in Table 1 in the Section 7.
7 Examples and tables
7.1 Examples
1° The Prism graph I(n, 1,1). We have the following asymptotic
T1,1(n) = n(T„(2) - 1) — |(2 + V3)n, n ^ to.
2° The generalized Petersen graph GP(n, 2) = I(n, 1,2). The the number of spanning
e T1,2(n) - f A?,2, n ^ c
7+ V5+ ^38 + 14V5
trees (see [19]) behaves like r1,2(n) — f Af,2, n ^ to, where
A1,2 = —^-—-!-— = 4.39026.
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 481
3° The smallest proper /-graph I(n, 2,3) has the following asymptotic for the number of spanning trees
T2,3(n) ^ 13^^ n ^ ^
Here A2,3 = 4.84199 is a suitable root of the algebraic equation
1 - 7x + 13x2 - 35x3 + 161x4 - 287x5 + 241x6 - 371x7 + 577x8 - 371x9 + 241x10 - 287X11 + 161x12 - 35x13 + 13x14 - 7x15 + x16 = 0.
Here is the table for asymptotic constants Ak,i for relatively prime numbers 1 < k <
l < 9.
Table 1: Asymptotic constants Afcjl
k\1	1	2	3	4	5	6	7	8	9
1	3.7320	4.3902	4.7201	4.8954	4.9953	5.0559	5.0945	5.1203	5.1382
2		-	4.8419	-	5.0249	-	5.1033	-	5.1414
3			-	5.0054	5.0541	-	5.1137	5.1320	-
4				-	5.0802	-	5.1244	-	5.1504
5					-	5.1201	5.1346	5.1461	5.1554
6						-	5.1438	-	-
7							-	5.1589	5.1649
8								-	5.1691
7.2 The tables of Jacobians of I-graphs
Theorem 4.1 is the first step to understand the structure of the Jacobian for I(n, k, l). Also, it gives a simple way for numerical calculations of Jac(I(n, k, l)) for small values of k and l. See Tables 2 and 3.
The first example of Jacobian Jac(I(n, 3,4)) with the maximum rank 13:
n = 170,
Jac(I(170, 3, 4)) = Z2 © Z8 © Z6108 ® Z30540 © Z22-3-5-103-509-1699 11593-pq
© Z22-3-5-17-103-509 -1699 -11593 p q,
and
T3,4(170) = 225 • 34 • 53 • 17 • 1032 • 5094 • 16992 • 115932 • p2 • q2
where p = 16901365279286026289 and q = 34652587005966540929.
482
Ars Math. Contemp. 15 (2018) 441-466
Table 2: Graph I(n, 2, 3).
n	Jac(I(n, 2, 3))	T2,3(n) = I Jac(I(n, 2, 3))|
4	Z7 e Z28	196
B	Z19 e Zg5	1S0B
6	Zlg e Z114	2166
T	Z83 e Z581	4S223
S	Zl6l e Z1288	20T36S
9	Z289 e Z260l	TB16S9
10	Zl558 e Z3895	606S410
11	Zl693 e Zl8623	31B2ST39
12	Z5 e Z5 e Z665 e Z7980	13266TB00
13	Z25 e Z325 e Z325 e Z325	SBS20312B
14	Z17513 e Z245182	4293ST2366
1B	Z37069 e Z556035	2061166141B
16	Z84847 e Z1357552	11B1S4214B44
1T	Z2 e Z23186 e Z394162	BS4S9SB6S44S
1S	Z400843 e Z7215174	2S921B19916S2
19	Z898243 e Z17066617	1B3299692B3931
20	Z4g e Z5453 e Zl09060	TTB02443441TS0
21	Z4301807 e Zg0337947	3SS616412TT0229
22	Zg536669 e Z209806718	2000SBT223B42342
23	Z20949827 e Z481846021	10094B90TS0BSS36T
24	Z5 e Z5 e Z9lg2295 e Z220615080	B0B9S9T242021B000
2B	Zl0l46853l e Z2536713275	2BT396B69BS244902B
26	Z25 e Z325 e Z8923525 e Zl7847050	12939T60994164062B0
2T	Z490309597 e Zl323835gllg	6490S94B24BTS16B043
2S	Z49 e Z154342069 e Z4321577932	326S30626S9111444092
29	Z2376466133 e Z68917517857	163TS014T1BTBS32369S1
30	Zlg e Zlg e Z275089049 e Z8252671470	S19B492B624T41B262S30
31	Zll507g604gl e Z356746775221	410B42TT94B3492BT93B11
32	Z25318259953 e Z810184318496	20B124BT1SBB2BST39906SS
33	Z5570038905l e Z1838112838683	1023S36002342S11024B9S33
34	Z2 e Z4 e Zlgl5580948 e Z32564876116	B11022336096BS23B2633SB6
3B	Z269747901677 e Zg44ll76558695	2B46T3TB660T00B60T9431B1B
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 483
Table 3: Graph I(n, 3,4).
n	Jac(I(n, 3,4))	73,4(n) = | Jac(I(n, 3, 4))|
5	Z2 © Z10 © Z10 © Z10	2000
6	Z19 © Z114	2166
7	Z71 © Z497	35287
8	Z73 © Z584	42632
9	Z289 © Z2601	751689
10	Z2 © Z12 © Z60 © Z60 © Z60	5184000
11	Z1541 © Z16951	26121491
12	Zn © Zn © Z209 © Z2508	63424812
13	Z5 © Z5 © Z1555 © Z20215	785858125
14	Z16969 © Z237566	4031257454
15	Z2 © Z10 © Z17410 © Z52230	18186486000
16	Z71321 © Z1141136	81386960656
17	Z2 © Z23186 © Z394162	584898568448
18	Z400843 © Z7215174	2892151991682
19	Z37 © Z37 © Z23939 © Z454841	14906272578931
20	Z8 © Z12 © Z120 © Z79080 © Z79080	72042006528000
21	Z4487981 © Z94247601	422981442583581
22	Z10002631 © Z220057882	2201157792287542
23	Z22138559 © Z509186857	11272663275719063
24	Z187 © Z187 © Z259369 © Z6224856	56458663080288216
25	Z2114 © Z52850 © Z52850 © Z52850	312061332000250000
484
Ars Math. Contemp. 15 (2018) 441-466
References
[1]	R. Bacher, P. de la Harpe and T. Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France 125 (1997), 167-198, http://www. numdam.org/item?id=BSMF_19 97_125_2_16 7_0.
[2]	M. Baker and S. Norine, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Notices 15 (2009), 2914-2955, doi:10.1093/imrn/rnp037.
[3]	N. Biggs, Three remarkable graphs, Canad. J. Math. 25 (1973), 397-411, doi:10.4153/ cjm-1973-040-1.
[4]	N. L. Biggs, Chip-flring and the critical group of a graph, J. Algebraic Combin. 9 (1999), 25-45, doi:10.1023/a:1018611014097.
[5]	M. Boben, T. Pisanski and A. Zitnik, I-graphs and the corresponding configurations, J. Combin. Des. 13 (2005), 406-424, doi:10.1002/jcd.20054.
[6]	F. T. Boesch and H. Prodinger, Spanning tree formulas and Chebyshev polynomials, Graphs Combin. 2 (1986), 191-200, doi:10.1007/bf01788093.
[7]	P. Chen, Y. Hou and C. Woo, On the critical group of the Mobius ladder graph, Australas. J. Combin. 36 (2006), 133-142, https://ajc.maths.uq.edu.au/pdf/3 6/ajc_v36_ p133.pdf.
[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]	R. Cori and D. Rossin, On the sandpile group of dual graphs, European J. Combin. 21 (2000), 447-459, doi:10.1006/eujc.1999.0366.
[10]	P. J. Davis, Circulant Matrices, AMS Chelsea Publishing, 2nd edition, 1994.
[11]	A. S. S. de Oliveira and C. T. M. Vinagre, The spectrum of an i-graph, 2015, arXiv:1511.03513 [math.CO].
[12]	D. Dhar, P. Ruelle, S. Sen and D.-N. Verma, Algebraic aspects of abelian sandpile models, J. Phys.A 28 (1995), 805-831, http://stacks.iop.org/0305-44 70/2 8/8 05.
[13]	G. Everestand T. Ward, Heights of Polynomials and Entropy in Algebraic Dynamics, Springer Science & Business Media, 2013, doi:10.1007/978-1-4471-3898-3.
[14]	R. M. Foster, The Foster Census, Charles Babbage Research Centre, Winnipeg, MB, 1988, with an introduction by I. Z. Bouwer, W. W. Chernoff, B. Monson and Z. Star.
[15]	R. Gera and P. Stanica, The spectrum of generalized Petersen graphs, Australas. J. Combin. 49
(2011),	39-45, https://ajc.maths.uq.edu.au/pdf/4 9/ajc_v4 9_p039.pdf.
[16]	B. Horvat, T. Pisanski and A. Zitnik, Isomorphism checking of I-graphs, Graphs Combin. 28
(2012),	823-830, doi:10.1007/s00373-011-1086-2.
[17]	Y. Hou, C. Woo and P. Chen, On the sandpile group of the square cycle C^, Linear Algebra Appl. 418 (2006), 457-467, doi:10.1016/j.laa.2006.02.022.
[18]	M. Kotani and T. Sunada, Jacobian tori associated with a finite graph and its abelian covering graphs, Adv. Appl. Math. 24 (2000), 89-110, doi:10.1006/aama.1999.0672.
[19]	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.
[20]	D. Lorenzini, Smith normal form and Laplacians, J. Comb. Theory Ser. B 98 (2008), 12711300, doi:10.1016/j.jctb.2008.02.002.
I. A. Mednykh: On Jacobian group and complexity of the I-graph I (n, k, l) through ... 
485
[21]	A. D. Mednykh and I. A. Mednykh, On the structure of the Jacobian group of circulant graphs, Dokl. Math. 94 (2016), 445-449, doi:10.1134/s106456241604027x.
[22]	I. A. Mednykh and M. A. Zindinova, On the structure of Picard group for Moebius ladder, Sib. Elektron. Mat. Izv. 8 (2011), 54-61, http://semr.math.nsc.ru/v8/p54-61.pdf.
[23]	S. D. Nikolopoulos and C. Papadopoulos, The number of spanning trees in Kn-complements of quasi-threshold graphs, Graphs Combin. 20 (2004), 383-397, doi:10.1007/ s00373-004-0568-x.
[24]	M. Petkovsek and H. Zakrajsek, Enumeration of I-graphs: Burnside does it again, Ars Math. Contemp. 2 (2009), 241-262, doi:10.26493/1855-3974.113.3dc.
[25]	R. Shrock and F. Y. Wu, Spanning trees on graphs and lattices in d dimensions, J. Phys. A 33 (2000), 3881-3902, doi:10.1088/0305-4470/33/21/303.
[26]	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.
[27]	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.
[28]	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.