On Jacobian group and complexity of the $Y$-graph

Y.S. Kwon, A.D. Mednykh, I.A. Mednykh

> Abstract. In the present paper we suggest a simple approach for counting
> Jacobian group of the $Y$-graph $Y(n;k,l,m).$ In the case $Y(n;1,1,1)$ the
> structure of the Jacobian group will be find explicitly. Also, we obtain a
> closed formula for the number of spanning trees of $Y$-graph in terms of
> Chebyshev polynomials and give its asymtotics.
>
> Keywords: spanning tree, Jacobian group, Laplacian matrix, Chebyshev
> polynomial, Mahler measure

##  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], [3], [4]). 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 simple
graphs such as the wheel, fan, prism, ladder, and Möebius ladder [5], grids
[6], lattices [7], Sierpinski gaskets [8, 9], 3-prism and 3-anti-prism [10]
and so on. At the same time, the structure of the Jacobian is known only in
particular cases [1], [3], [11], [12], [13], [14] and [15].

We mention that the number of spanning trees for circulant graphs is expressed
in terms of the Chebyshev polynomials; it was found in [16], [17], [18], [19]
and [20]. More generally, this result also holds for arbitrary cyclic
coverings of a graph [21]. In particular, (see [22] and [23]) this is true for
the generalized Petersen graph $GP(n,k)$ and $I$-graph $I(n,j,k).$ These two
graphs are expansions of the tree consisting of a single edge. In the same
time, there is a wide family of cubic graphs that are expansions of the tree
consisting of more than one edge. Three families of such graphs were
discovered by Biggs [24]. He calls these graphs the $I$-graph, $Y$-graph, and
$H$-graph, because of the method by which the graphs were created. This method
of construction was generalized in [25]. In the present paper we investigate
the structure of Jacobian and find the number of spanning trees for a
$Y$-graph. The similar questions for $H$-graphs will be considered in the
forthcoming paper by the authors.

A $Y$-graph $Y(n;k,l,m)$ has $4n$ vertices arranged in four segments of $n$
vertices. Let the vertices be $v_{x,y}$ for $x=0,1,2,3,$ and $y$ in the
integers modulo $n.$ Call the graph induced by the $v_{x,y}$ for a fixed $x,$
the $x$-segment. The $0$-segment is called the $\it inner\,segment$ and
consists of $n$ independent vertices; while each of the other three segments
is called an outer segment. These three segments consist of outer edges which
join each $v_{1,y}$ to $v_{1,y+k},$ each $v_{2,y}$ to $v_{2,y+l},$ and each
$v_{3,y}$ to $v_{3,y+m},$ where the subscript addition is performed modulo
$n.$ Each outer vertex $v_{i,y}$ is joined to the inner vertex $v_{0,y}$ by an
inner edge. Thus $Y(n;k,l,m)$ consists of $n$ inner vertices, $3n$ outer
vertices, $3n$ inner edges, and $3n$ outer edges. For this definition to
produce a connected graph it is necessary that $\gcd(k,l,m,n)=1$, where
$\gcd(k,l,m,n)$ is the greatest cmmon divisor of $k,l,m$ and $n$. In what
follows, we restrict ourselves by connected graphs only.

In this paper, we find an approach for counting Jacobian group of the
$Y$-graph $Y(n;k,l,m).$ It the case $Y(n;1,1,1)$ the structure of the Jacobian
group will be find explicitly. Also, we obtain a closed formula for the number
of spanning trees of $Y$-graph in terms of Chebyshev polynomials.

##  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\in V(G),$ we set $a_{uv}$ to be equal to the number
of edges between vertices $u$ and $v.$ The matrix $A=A(G)=\\{a_{uv}\\}_{u,v\in
V(G)}$ is called the adjacency matrix of the graph $G.$ The degree $d(v)$ of a
vertex $v\in V(G)$ is defined by $d(v)=\sum_{u\in V(G)}a_{uv}.$ Let $D=D(G)$
be the diagonal matrix indexed by the elements of $V(G)$ with $d_{vv}=d(v).$
The matrix $L=L(G)=D(G)-A(G)$ is called the Laplacian matrix, or simply
Laplacian, of the graph $G.$

Recall [11] 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 $\mathbb{Z}^{|V|}\to\mathbb{Z}^{|V|},$ where
$|V|=|V(G)|$ is the number of vertices in $G.$ The cokernel
$\textrm{coker}\,(L(G))=\mathbb{Z}^{|V|}/\textrm{im}\,(L(G))$ is an abelian
group. Let

$\textrm{coker}\,(L(G))\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}}\oplus\cdots\oplus\mathbb{Z}_{d_{|V|}}$

be its Smith normal form satisfying the conditions
$d_{i}\big{|}d_{i+1},\,(1\leq i\leq|V|-1).$ If the graph is connected, then
the groups
${\mathbb{Z}}_{d_{1}},{\mathbb{Z}}_{d_{2}},\ldots,{\mathbb{Z}}_{d_{|V|-1}}$
are finite, and $\mathbb{Z}_{d_{|V|}}=\mathbb{Z}.$ In this paper, we define
Jacobian group $Jac(G)$ as the torsion subgroup of $\textrm{coker}\,(L(G)).$
In other words,

$Jac(G)\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}}\oplus\cdots\oplus\mathbb{Z}_{d_{|V|-1}}.$

Let $M$ be an integer $n\times n$ matrix, then we can interpret $M$ as
$\mathbb{Z}$-linear operator from $\mathbb{Z}^{n}$ to $\mathbb{Z}^{n}.$ In
this interpretation $M$ has a kernel $\textrm{ker}M,$ an image
$\textrm{im}\,M,$ and a cokernel
$\textrm{coker}M=\mathbb{Z}^{n}/\textrm{im}\,M.$ We emphasize that
$\textrm{coker}\,M$ of the matrix $M$ is completely determined by its Smith
normal form. In particular, if matrices $M$ and $M^{\prime}$ are elementary
equivalent then $\textrm{coker}\,M\cong\textrm{coker}\,M^{\prime}.$

In what follows, by $I_{n}$ we denote the identity matrix of order $n.$

We call an $n\times n$ matrix circulant, and denote it by
$circ(a_{0},a_{1},\ldots,a_{n-1})$ if it is of the form

$circ(a_{0},a_{1},\ldots,a_{n-1})=\left(\begin{array}[]{ccccc}a_{0}&a_{1}&a_{2}&\ldots&a_{n-1}\\\
a_{n-1}&a_{0}&a_{1}&\ldots&a_{n-2}\\\ &\vdots&&\ddots&\vdots\\\
a_{1}&a_{2}&a_{3}&\ldots&a_{0}\\\ \end{array}\right).$

Recall [26] that the eigenvalues of matrix
$C=circ(a_{0},a_{1},\ldots,a_{n-1})$ are given by the following simple
formulas $\lambda_{j}=p(\varepsilon^{j}_{n}),\,j=0,1,\ldots,n-1$ where
$p(x)=a_{0}+a_{1}x+\ldots+a_{n-1}x^{n-1}$ and $\varepsilon_{n}$ is an order
$n$ primitive root of the unity. Moreover, the circulant matrix $C=p(T),$
where $T=circ(0,1,0,\ldots,0)$ is the matrix representation of the shift
operator
$T:(x_{0},x_{1},\ldots,x_{n-2},x_{n-1})\rightarrow(x_{1},x_{2},\ldots,x_{n-1},x_{0}).$

##  3 The structure of Jacobian group for the graph $Y(n;k,l,m)$

To investigate the Laplacian matrix of graph $Y(n;k,l,m)$, we denote by
$T=circ(0,1,\ldots,0)$ the $n\times n$ shift operator. Then the Laplacian
$L=L(Y(n;k,l,m))$ can be represented in the form

$L=\left(\begin{array}[]{cccc}3I_{n}&-I_{n}&-I_{n}&-I_{n}\\\ -I_{n}&A&0&0\\\
-I_{n}&0&B&0\\\ -I_{n}&0&0&C\\\ \end{array}\right),$

where $A=3I_{n}-T^{-k}-T^{k},B=3I_{n}-T^{-l}-T^{l},\text{ and
}C=3I_{n}-T^{-m}-T^{m}.$

Recall that $Jac(Y(n;k,l,m))$ is given by the torsion subgroup of the
$coker(L),$ where $L$ is considered as $\mathbb{Z}$-linear operator from
$\mathbb{Z}^{4n}$ to itself. To find the structure of $coker(L)$ consider the
following $n$-tuples of variables
$x=(x_{1},\ldots,x_{n}),\,y=(y_{1},\ldots,y_{n}),\,s=(s_{1},\ldots,s_{n})$ and
$t=(t_{1},\ldots,t_{n}).$ As an abelian group, $coker(L)$ has the following
presentation

$coker(L)=\langle x,y,s,t|L(x,y,s,t)^{t}=0\rangle.$

Hence,

$coker(L)=\langle x,y,s,t|3x-y-s-t=0,\,-x+Ay=0,\,-x+Bs=0,\,-x+Ct=0\rangle.$

Since $x=Bs,$ we can eliminate the set of variables $x=(x_{1},\ldots,x_{n})$
from the above presentation to get

$coker(L)=\langle y,s,t|3Bs-s-t-y=0,\,-Bs+Ay=0,\,-Bs+Ct=0\rangle.$

Eliminating $y=3Bs-s-t$ we also obtain

$coker(L)=\langle s,t|(-A-B+3AB)s-At=0,\,-Bs+Ct=0\rangle.$ (1)

This leads to the main result of this section.

###### Theorem 1

The group $Jac(Y(n;k,l,m))$ is isomorphic to the torsion subgroup of the
$coker(M),$ where $M$ is the $2n\times 2n$ block matrix given by

$M=\left(\begin{array}[]{cc}-A-B+3AB&-A\\\ -B&C\\\ \end{array}\right),$

where $A=3I_{n}-T^{-k}-T^{k},\,B=3I_{n}-T^{-l}-T^{l},\text{ and
}C=3I_{n}-T^{-m}-T^{m}.$

##  4 Explicit formulas for Jacobian of the graph $Y(n;1,1,1)$

We apply the results obtained in previous section to find explicit formulas
for Jacobian of the graph $Y(n;1,1,1).$ The main result of this section is the
following theorem.

###### Theorem 2

Jacobian group $J_{n}=Jac(Y(n;1,1,1)),\,n\geq 4$ of the graph $Y(n;1,1,1)$ has
the following structure

  1. $1^{0}$

$J_{n}\cong\mathbb{Z}_{3}^{n-4}\oplus\mathbb{Z}_{3n}\oplus\mathbb{Z}_{L_{n}}^{2}\oplus\mathbb{Z}_{3L_{n}}^{2},$
if $n$ is odd,

  2. $2^{0}$

$J_{n}\cong\mathbb{Z}_{3}^{n-4}\oplus\mathbb{Z}_{3n}\oplus\mathbb{Z}_{F_{n}}\oplus\mathbb{Z}_{3F_{n}}\oplus\mathbb{Z}_{5F_{n}}\oplus\mathbb{Z}_{15F_{n}},$
$n$ is even,

where $L_{n}$ and $F_{n}$ are the Lucas and the Fibonacci numbers
respectively.

The proof of the theorem is based on some auxiliary results. We start with the
following result which is a direct consequence of Theorem 1.

###### Proposition 1

The group $Jac(Y(n;1,1,1))$ is isomorphic to the torsion subgroup of the
abelian group $coker(3(A^{2}-A))\oplus coker(A),$ where $A=3I_{n}-T-T^{-1}.$

Proof Since $A=B=C=3I_{n}-T-T^{-1},$ by (1) we have

$coker(L)=\langle s,t|(3A^{2}-2A)s-At=0,\,-As+At=0\rangle.$ (2)

Substituting $t=s+u$ in (2) we obtain

$\displaystyle coker(L)$ $\displaystyle=$ $\displaystyle\langle
s,u|(3A^{2}-3A)s-Au=0,\,Au=0\rangle=\langle s,u|(3(A^{2}-A)s=0,\,Au=0\rangle$
$\displaystyle=$ $\displaystyle\langle s|(3(A^{2}-A)s=0\rangle\oplus\langle
u|\,Au=0\rangle=coker(3(A^{2}-A))\oplus coker(A).$

Also, we need the following version of Theorem 2.1(iv) from [27].

###### Proposition 2

Let $T=circ(0,1,0,\ldots,0)$ be the $n$ by $n$ shift operator and $a$ and $b$
be non-zero integers. We set $C_{n}(a,b)=aI_{n}+bT+bT^{-1}.$ Then
$coker\,C_{n}(a,b)\cong coker\,C,$ where

$C=\begin{cases}b^{\frac{n}{2}-1}u(n)\left(\begin{array}[]{cc}a&2b\\\ 2b&a\\\
\end{array}\right)&\textrm{if }$n$\textrm{ is even }\\\
b^{\frac{n-1}{2}}t(n)\left(\begin{array}[]{cc}1&0\\\ 0&a+2b\\\
\end{array}\right)&\textrm{if }$n$\textrm{ is odd,}\end{cases}$

$u(n)=\frac{\sin(\frac{n}{2}\arccos(x))}{\sin(\arccos(x))},\,\,t(n)=\frac{\cos(\frac{n}{2}\arccos(x))}{\cos(\frac{1}{2}\arccos(x))}\text{
and }x=\frac{a}{2b}.$

Proof Consider a two-variable Chebyshev polynomial $f_{n}(x,y)$ defined by the
following recursion

$f_{n}(x,y)=xf_{n-1}(x,y)-y^{2}f_{n-2}(x,y),\,f_{-1}(x,y)=1,\,f_{0}(x,y)=0.$

One can check that $f_{n}(x,y)=y^{n}U_{n}(\frac{x}{2y}),$ where $U_{n}(z)$ is
the Chebyshev polynomial of the second kind. By ([27], Theorem 2.1(iv)) we
have $coker\,C_{n}(a,b)\cong coker\,C,$ where

$C=\begin{cases}f_{\frac{n}{2}-1}(a,b)\left(\begin{array}[]{cc}a&2b\\\ 2b&a\\\
\end{array}\right)&\textrm{if }n\textrm{ is even}\\\
(f_{\frac{n-1}{2}}(a,b)-bf_{\frac{n-3}{2}}(a,b))\left(\begin{array}[]{cc}1&0\\\
0&a+2b\\\ \end{array}\right)&\textrm{if }n\textrm{ is odd,}\end{cases}$

To finish the proof we have to show that
$f_{\frac{n}{2}-1}(a,b)=b^{\frac{n}{2}-1}u(n)$ and
$f_{\frac{n-1}{2}}(a,b)-bf_{\frac{n-3}{2}}(a,b)=b^{\frac{n}{2}-1}t(n),$ where
$u(n)$ and $t(n)$ are the same as in the statement of Proposition. The first
equality easily follows from the definition of Chebyshev polynomial, since

$U_{\frac{n}{2}-1}(x)=\frac{\sin(\frac{n}{2}\arccos(x))}{\sin(\arccos(x))}.$

To prove the second we note that
$f_{\frac{n-1}{2}}(a,b)=b^{\frac{n-1}{2}}U_{\frac{n-1}{2}}(x)=b^{\frac{n-1}{2}}\frac{\sin(\frac{n+1}{2}\arccos(x))}{\sin(\arccos(x))}.$
Hence,

$f_{\frac{n-1}{2}}(a,b)-bf_{\frac{n-3}{2}}(a,b)=b^{\frac{n-1}{2}}\left(\frac{\sin(\frac{n+1}{2}\arccos(x))}{\sin(\arccos(x))}-\frac{\sin(\frac{n-1}{2}\arccos(x))}{\sin(\arccos(x))}\right)$

$=2b^{\frac{n-1}{2}}\left(\frac{\cos(\frac{n}{2}\arccos(x))\sin(\frac{1}{2}\arccos(x))}{\sin(\arccos(x))}\right)=b^{\frac{n-1}{2}}\frac{\cos(\frac{n}{2}\arccos(x))}{\cos(\frac{1}{2}\arccos(x))}.$

The following two lemmas are immediate consequences of Proposition 2.

###### Lemma 1

Let $T=circ(0,1,0,\ldots,0)$ be the $n$ by $n$ shift operator. We set
$A(n)=3I_{n}-T^{-1}-T.$ Then cokernel of $A(n)$ is given by the following
formulas

  1. (i)

$coker\,A(n)\cong\mathbb{Z}_{F_{n}}\oplus\mathbb{Z}_{5F_{n}}$ if $n$ is even,

  2. (ii)

$coker\,A(n)\cong\mathbb{Z}_{L_{n}}\oplus\mathbb{Z}_{L_{n}}$ if $n$ is odd,

where $F_{n}$ and $L_{n}$ are the Fibonacci and the Lucas numbers
respectively.

Proof Since $A(n)=C_{n}(3,-1),$ we have $coker\,A(n)\cong coker(C),$ where $C$
is the same as in Proposition 2, with $a=3$ and $b=-1.$ Then for $n$ even we
get

$b^{\frac{n}{2}-1}u(n)=(-1)^{\frac{n}{2}-1}\frac{\sin(\frac{n}{2}\arccos(-\frac{3}{2}))}{\sin(\arccos(-\frac{3}{2}))}=\frac{1}{\sqrt{5}}\left((\frac{\sqrt{5}+1}{2})^{n}-(\frac{\sqrt{5}-1}{2})^{n}\right)=F_{n},$

and for $n$ odd

$b^{\frac{n-1}{2}}t(n)=(-1)^{\frac{n-1}{2}}\frac{\cos(\frac{n}{2}\arccos(-\frac{3}{2}))}{\cos(\frac{1}{2}\arccos(-\frac{3}{2}))}=(\frac{\sqrt{5}+1}{2})^{n}-(\frac{\sqrt{5}-1}{2})^{n}=L_{n}.$

Hence, $C=\left(\begin{array}[]{cc}3F_{n}&-2F_{n}\\\ -2F_{n}&3F_{n}\\\
\end{array}\right)$ if $n$ is even and $C=\left(\begin{array}[]{cc}L_{n}&0\\\
0&L_{n}\\\ \end{array}\right)$ if $n$ is odd. We note that matrix
$\left(\begin{array}[]{cc}3&-2\\\ -2&3\\\ \end{array}\right)$ is elementary
equivalent to matrix $\left(\begin{array}[]{cc}1&0\\\ 0&5\\\
\end{array}\right).$ Therefore,
$coker(C)\cong\mathbb{Z}_{F_{n}}\oplus\mathbb{Z}_{5F_{n}}$ if $n$ is even and
$coker(C)\cong\mathbb{Z}_{L_{n}}\oplus\mathbb{Z}_{L_{n}}$ if $n$ is odd. The
lemma is proved.

By similar arguments we get the following result.

###### Lemma 2

Let $T=circ(0,1,0,\ldots,0)$ and $B(n)=2I_{n}-T^{-1}-T.$ Then for $n\geq 2$ we
have

$coker\,B(n)\cong\mathbb{Z}_{n}\oplus\mathbb{Z}.$

We also need the following elementary lemma.

###### Lemma 3

Let $D={diag}(d_{1},d_{2},\ldots,d_{n})$ be an integer $n\times n$ diagonal
matrix and $k$ be a positive integer. Then

$coker(kD)\cong\mathbb{Z}_{kd_{1}}\oplus\mathbb{Z}_{kd_{2}}\ldots\oplus\mathbb{Z}_{kd_{n}}.$

Now, we are able to complete the proof of Theorem 2. Indeed, by Proposition 1
$coker(L)=coker(3(A^{2}-A))\oplus coker(A).$ The structure of $coker(A)$ is
described in Lemma 1. Also, Lemma 2 gives us
$coker(A-I)\cong\mathbb{Z}_{n}\oplus\mathbb{Z},$ where $I=I_{n}.$

We note that the matrices $\left(\begin{array}[]{cc}A&0\\\ I&A-I\\\
\end{array}\right)$ and $\left(\begin{array}[]{cc}A&0\\\ 0&A-I\\\
\end{array}\right)$ are elementary equivalent.

Hence, $coker(A(A-I))\cong coker(A)\oplus coker(A-I).$ By Lemmas 1 and 2,
$coker(A(A-I))\cong\mathbb{Z}_{F_{n}}\oplus\mathbb{Z}_{5F_{n}}\oplus\mathbb{Z}_{n}\oplus\mathbb{Z}$
if $n$ is even and
$coker(A(A-I))\cong\mathbb{Z}_{L_{n}}\oplus\mathbb{Z}_{L_{n}}\oplus\mathbb{Z}_{n}\oplus\mathbb{Z}$
if $n$ is odd. This means that matrix $A(A-I)$ is elementary equivalent to the
matrix

${diag}(\underbrace{1,\ldots,1}_{(n-4)\,times},F_{n},5F_{n},n,0)$

in the first case and to the matrix

${diag}(\underbrace{1,\ldots,1}_{(n-4)\,times},L_{n},L_{n},n,0)$

in the latter. Then, by making use of Lemma 3, we get
$coker(3A(A-I))\cong\mathbb{Z}_{3}^{n-4}\oplus\mathbb{Z}_{3F_{n}}\oplus\mathbb{Z}_{15F_{n}}\oplus\mathbb{Z}_{3n}\oplus\mathbb{Z}$
if $n$ is even and
$coker(3A(A-I))\cong\mathbb{Z}_{3}^{n-4}\oplus\mathbb{Z}_{3L_{n}}\oplus\mathbb{Z}_{3L_{n}}\oplus\mathbb{Z}_{3n}\oplus\mathbb{Z}$
if $n$ is odd. Once more, by Lemma 1 we have
$coker(A)\cong\mathbb{Z}_{F_{n}}\oplus\mathbb{Z}_{5F_{n}}$ if $n$ is even and
$coker(A)\cong\mathbb{Z}_{L_{n}}\oplus\mathbb{Z}_{L_{n}}$ if $n$ is odd.

Combine these results we finish the proof of the theorem.

##  5 Counting the number of spanning trees for the graph $Y(n;k,l,m)$

###### Theorem 3

The number of spanning trees $\tau_{k,l,m}(n)$ in the graph $Y(n;k,l,m)$ is
given by the formula

$\tau_{k,l,m}(n)=\frac{n\,3^{n}}{k^{2}+l^{2}+m^{2}}\prod_{p=1}^{s}|2T_{n}(w_{p})-2|,$

hereby $s=k+l+m-1,$ and $\,w_{p}=1,2,\ldots,s$ are roots of the order $s$
algebraic equation $Q(w)=0,$ where

$Q(w)=\frac{(3-2T_{k}(w))(3-2T_{l}(w))(3-2T_{m}(w))}{w-1}\left(3-\frac{1}{3-2T_{k}(w)}-\frac{1}{3-2T_{l}(w)}-\frac{1}{3-2T_{m}(w)}\right)$

and $T_{k}(w)$ is the Chebyshev polynomial of the first kind.

Proof: By the celebrated Kirchhoff theorem, the number of spanning trees
$\tau_{k,\,l,\,m}(n)$ is equal to the product of nonzero eigenvalues of the
Laplacian of a graph $Y(n;k,l,m)$ divided by the number of its vertices $4n.$
To investigate the spectrum of Laplacian matrix, we denote by
$T=circ(0,1,\ldots,0)$ the $n\times n$ shift operator. The the Laplacian
$L=L(Y(n;k,l,m))$ is given by the matrix

$L=\left(\begin{array}[]{cccc}3I_{n}&-I_{n}&-I_{n}&-I_{n}\\\
-I_{n}&3I_{n}-T^{-k}-T^{k}&0&0\\\ -I_{n}&0&3I_{n}-T^{-l}-T^{l}&0\\\
-I_{n}&0&0&3I_{n}-T^{-m}-T^{m}\\\ \end{array}\right).$

The eigenvalues of circulant matrix $T$ are
$\varepsilon_{n}^{j},\,j=0,1,\ldots,n-1,$ where $\varepsilon_{n}=e^{\frac{2\pi
i}{n}}.$ Since all of them are distinct, the matrix $T$ is conjugate to the
diagonal matrix
$\mathbb{T}=diag(1,\varepsilon_{n},\ldots,\varepsilon_{n}^{n-1})$ with
diagonal entries $1,\varepsilon_{n},\ldots,\varepsilon_{n}^{n-1}$. To find
spectrum of $L,$ without loss of generality, one can assume that
$T=\mathbb{T}.$ Then the $n\times n$ blocks of $L$ are diagonal matrices. This
essentially simplifies the problem of finding eigenvalues of $L.$ Indeed, let
$\lambda$ be an eigenvalue of $L$ and
$(x,y,z,t)=(x_{1},\ldots,x_{n},y_{1},\ldots,y_{n},z_{1},\ldots,z_{n},t_{1},\ldots,t_{n})$
be the respective eigenvector. Then we have the following system of equations

$\left\\{\begin{array}[]{ccccc}(3-\lambda)x&-y&-z&-t&=0\\\
-x&+(A-\lambda)y&{}\hfil&{}\hfil&=0\\\ -x&{}\hfil&+(B-\lambda)z&{}\hfil&=0\\\
-x&{}\hfil&{}\hfil&+(C-\lambda)t&=0\\\ \end{array}\right.,$

where $A=3I_{n}-T^{-k}-T^{k},\,B=3I_{n}-T^{-l}-T^{l},\text{ and
}C=3I_{n}-T^{-m}-T^{m}.$

Consequently eliminating $y,z$ and $t$ from the above equation, we obtain

$((3-\lambda)(A-\lambda)(B-\lambda)(C-\lambda)-(A-\lambda)(B-\lambda)-(B-\lambda)(C-\lambda)-(A-\lambda)(C-\lambda))x=0.$

Recall that the matrices under consideration are diagonal and the
$(j+1,j+1)$-th entry of $T$ is equal to $\varepsilon_{n}^{j}.$ Consider the
following two variable Laurent polynomial

$P(z,\lambda)=(3-\lambda)(a-\lambda)(b-\lambda)(c-\lambda)-(a-\lambda)(b-\lambda)-(b-\lambda)(c-\lambda)-(a-\lambda)(c-\lambda),$

where $a=3-z^{k}-z^{-k},\,b=3-z^{l}-z^{-l}$ and $c=3-z^{m}-z^{-m}.$

Then, for any $j=0,\ldots,n-1,$ matrix $L$ has four eigenvalues, say
$\lambda_{1,j},\lambda_{2,j},\lambda_{3,j},$ and $\lambda_{4,j},$ satisfying
the order three algebraic equation $P(\varepsilon_{n}^{j},\lambda)=0.$ In
particular, if $j=0$ for
$\lambda_{1,0},\lambda_{2,0},\lambda_{3,0},\lambda_{4,0}$ we have
$\lambda(\lambda-1)^{2}(\lambda-4)=0.$ Thus,
$\lambda_{1,0}=0,\lambda_{2,0}=1,\lambda_{3,0}=1,$ and $\lambda_{4,0}=4.$

Let ${\bf e}_{j}=(0,\ldots,\underbrace{1}_{j-th},\ldots,0),\,j=1,\ldots,n.$
For given $\lambda=\lambda_{i,j}$ the corresponding eigenvector is
$(x,y,z,t),$ where $x={\bf e}_{j+1},y=(B-\lambda)(C-\lambda){\bf
e}_{j+1},z=(A-\lambda)(C-\lambda){\bf e}_{j+1},$ and
$t=(A-\lambda)(B-\lambda){\bf e}_{j+1}.$

By Vieta’s theorem, the product
$\pi_{j}=\lambda_{1,j}\lambda_{2,j}\lambda_{3,j}\lambda_{4,j}$ is given by the
formula $\pi_{j}=P(\varepsilon_{n}^{j}),$ where $P(z)=P(z,0).$

Now we have

$\tau_{k,\,l,\,m}(n)=\frac{1}{4n}\lambda_{2,0}\lambda_{3,0}\lambda_{4,0}\prod\limits_{j=1}^{n-1}\lambda_{1,j}\lambda_{2,j}\lambda_{3,j}\lambda_{4,j}=\frac{1}{n}\prod\limits_{j=1}^{n-1}\pi_{j}=\frac{1}{n}\prod\limits_{j=1}^{n-1}P(\varepsilon_{n}^{j}).$

To continue the calculation of $\tau_{k,\,l,\,m}(n)$ we need the following two
lemmas.

###### Lemma 4

The following identity holds $P(z)=(w-1)Q(w),$ where $Q(w)$ is an order
$k+l+m-1$ integer polynomial given by the formula

$Q(w)=\frac{(3-2T_{k}(w))(3-2T_{l}(w))(3-2T_{m}(w))}{w-1}\left(3-\frac{1}{3-2T_{k}(w)}-\frac{1}{3-2T_{l}(w)}-\frac{1}{3-2T_{m}(w)}\right),$

$T_{k}(w)$ is the Chebyshev polynomial of the first kind and
$w=\frac{1}{2}(z+z^{-1}).$

Proof Recall that $P(z)=3abc-ab-bc-ac,$ where
$a=3-z^{k}-z^{-k},\,b=3-z^{l}-z^{-l}$ and $c=3-z^{m}-z^{-m}.$ Let us
substitute $z=e^{i\varphi}.$ It is easy to see that
$w=\frac{1}{2}(z+z^{-1})=\cos\varphi,$ so we have $T_{k}(w)=\cos(k\arccos
w)=\cos(k\varphi)=\frac{1}{2}(z^{k}+z^{-k})$. Then the statement of the lemma
follows from elementary calculations.

Note that the leading term of Laurent polynomial $P(z)$ is $-3z^{k+l+m}.$ By
Lemma 4, $P(z)=(w-1)Q(w),$ where $w=\frac{1}{2}(z+z^{-1})$ and $Q(w)$ is a
polynomial of degree $s=k+l+m-1$. We have $w-1=\frac{(z-1)^{2}}{2z}$. Since
$Q(1)=\lim_{w\to 1}Q(w)=-2(k^{2}+l^{2}+m^{2})\neq 0,$ polynomial $P(z)$ has
the root $z=1$ with multiplicity two. Hence, all the roots of $P(z)$ are
$1,1,z_{1},1/z_{1},\ldots,z_{s},1/z_{s},$ where for all
$p=1,\ldots,s,z_{p}\neq 1.$ We get

$P(z)=\frac{-3(z-1)^{2}}{z^{k+l+m}}\prod\limits_{p=1}^{s}(z-z_{p})(z-z_{p}^{-1}).$

Also, $w_{p}=\frac{1}{2}(z_{p}+z_{p}^{-1}),\,p=1,\ldots,s$ are all the roots
of the equation $Q(w)=0.$ We set
$H(z)=\prod\limits_{p=1}^{s}(z-z_{p})(z-z_{p}^{-1}).$ Then
$P(z)=\frac{-3(z-1)^{2}}{z^{k+l+m}}H(z).$

The following lemma has been proved in ([22], Lemma 5.3).

###### Lemma 5

Let $H(z)=\prod\limits_{p=1}^{s}(z-z_{p})(z-z_{p}^{-1})$ and $H(1)\neq 0$.
Then

$\prod\limits_{j=1}^{n-1}H(\varepsilon_{n}^{j})=\prod\limits_{p=1}^{s}\frac{T_{n}(w_{p})-1}{w_{p}-1},$

where $w_{p}=\frac{1}{2}(z_{p}+z_{p}^{-1}),\,p=1,\ldots,k$ and $T_{n}(x)$ is
the Chebyshev polynomial of the first kind.

Note that
$\prod\limits_{j=1}^{n-1}(\varepsilon_{n}^{j}-1)^{2}=\lim\limits_{z\to
1}\prod\limits_{j=1}^{n-1}(z-\varepsilon_{n}^{j})^{2}=\lim\limits_{z\to
1}(\frac{z^{n}-1}{z-1})^{2}=n^{2}$ and
$\prod\limits_{j=1}^{n-1}\varepsilon_{n}^{j}=(-1)^{n-1}$. As a result, taking
into account Lemma 5, we obtain

$\displaystyle\tau_{k,l,m}(n)$ $\displaystyle=$
$\displaystyle\frac{1}{n}\prod\limits_{j=1}^{n-1}P(\varepsilon_{n}^{j})=\frac{1}{n}\prod\limits_{j=1}^{n-1}\frac{(-3)(\varepsilon_{n}^{j}-1)^{2}}{(\varepsilon_{n}^{j})^{s+1}}H(\varepsilon_{n}^{j})$
$\displaystyle=$
$\displaystyle\frac{(-1)^{s(n-1)}3^{n-1}n^{2}}{n}\prod\limits_{j=1}^{n-1}H(\varepsilon_{n}^{j})=(-1)^{s(n-1)}3^{n-1}n\prod\limits_{p=1}^{s}\frac{T_{n}(w_{p})-1}{w_{p}-1}.$

We note that $w_{p},\,p=1,\ldots,s$ are all the roots of the polynomial $Q(w)$
is an order $s=k+l+m-1$ whose leading term is $-3\cdot 2^{k+l+m}.$ We also
have $Q(1)=-2(k^{2}+l^{2}+m^{2}).$ Hence

$\prod\limits_{p=1}^{s}(w_{p}-1)=\frac{(-1)^{s}Q(1)}{-3\cdot
2^{k+l+m}}=\frac{k^{2}+l^{2}+m^{2}}{3\cdot(-2)^{s}}.$

Finally,

$\tau_{k,l,m}(n)=(-1)^{ns}\frac{n\,3^{n}2^{s}}{k^{2}+l^{2}+m^{2}}\prod_{p=1}^{s}(T_{n}(w_{p})-1)=\frac{n\,3^{n}}{k^{2}+l^{2}+m^{2}}\prod_{p=1}^{s}|2T_{n}(w_{p})-2|.$

##  6 Asymptotic formulas for the number of spanning trees $\tau_{k,l,m}(n)$

Consider Laurent polynomial $P(z)=3abc-ab-ac-bc,$ where
$a=3-z^{k}-z^{-k},\,b=3-z^{l}-z^{-l}$ and $c=3-z^{m}-z^{-m}$ from the above
section. We get the following result.

###### Theorem 4

The asymptotic behaviour for number of spanning trees $\tau_{k,l,m}(n)$ for
the graph $Y(n;k,l,m)$ with $\gcd(k,l,m)=1$ is given by the formula

$\tau_{k,l,m}(n)\sim\frac{n}{k^{2}+l^{2}+m^{2}}A_{k,l,m}^{n},\,n\to\infty,$

where $A_{k,l,m}=|a_{0}|\prod\limits_{P(z)=0,\,|z|>1}|z|,$ where the product
is taken over roots of the Laurent polynomial $P(z)$ and $a_{0}$ is the
leading coefficient of $P(z).$

We note that number $A_{k,l,m}$ coincides with the Mahler measure of
polynomial $P(z).$ Hence

$A_{k,l,m}=\exp\left({\int\limits_{0}^{1}\log|P(e^{2\pi
it})|\textrm{d}t}\right).$

Proof By Theorem 3 we have
$\tau_{k,l,m}(n)=\frac{n\,3^{n}}{k^{2}+l^{2}+m^{2}}\prod_{p=1}^{s}|2T_{n}(w_{p})-2|,$
where $w_{j},\,j=1,2,\ldots,s$ are all the roots of the polynomial $Q(w).$
Recall $P(z)=(w-1)Q(w),$ where $w=\frac{1}{2}(z+\frac{1}{z}).$ All the roots
of the polynomial $(w-1)Q(w)$ are $w_{j}=\frac{1}{2}(z_{j}+z_{j}^{-1}),$ where
$z_{j}$ and $1/z_{j},\,j=1,\ldots,s+1$ are all the roots of the polynomial
$P(z).$ One can check that $P(z)$ has $1$ as a root of multiplicity two.
Indeed, $P(1)=P^{\prime}(1)=0$ and
$P^{\prime\prime}(1)=-2(k^{2}+l^{2}+m^{2})\neq 0.$ So, we can assume that
$z_{j}\neq 1,\,j=1,2,\ldots,s.$ Since $\gcd(k,l,m)=1,$ taking into account the
arguments from Lemma 5.2 in [23] we get $|z_{j}|\neq 1,\,j=1,2,\ldots,s.$

We have $T_{n}(w_{j})=\frac{1}{2}(z_{j}^{n}+z_{j}^{-n}).$ Replacing $z_{j}$ by
$1/z_{j},$ if necessary, we always can assume that $|z_{j}|>1$ for all
$j=1,2,\ldots,s.$ Then $T_{n}(w_{j})\sim\frac{1}{2}z_{j}^{n}$ and
$|2T_{n}(w_{j})-2|\sim|z_{j}|^{n}$ as $n\to\infty.$ Hence

$3^{n}\prod_{j=1}^{s}|2T_{n}(w_{j})-2|\sim
3^{n}\prod_{j=1}^{s}|z_{j}|^{n}=3^{n}\prod\limits_{P(z)=0,\,|z|>1}|z|^{n}=A_{k,l,m}^{n}.$

The leading coefficient $a_{0}$ of the polynomial $P(z)$ is $3.$ So
$A_{k,l,m}=3\prod\limits_{P(z)=0,\,|z|>1}|z|$ is the Mahler measure of the
polynomial $P(z).$ By ([28], p. 67), we have
$A_{k,l,m}=\exp\left(\int\limits_{0}^{1}\log|P(e^{2\pi
it})|\textrm{d}t\right).$ The theorem is proved.

##  7 Examples

###  7.1 Graph $Y(n,1,1,1)$

Note that number $\tau_{1,1,1}(n)$ of spanning trees in the graph $Y(n,1,1,1)$
coinsides with the size of its Jacobian $J_{n}.$ As a consequence of theorem 2
we obtain

  1. $1^{0}$

$\tau_{1,1,1}(n)=3^{n-1}n\,L_{n}^{4},$ if $n$ is odd, and

  2. $2^{0}$

$\tau_{1,1,1}(n)=25\cdot 3^{n-1}n\,F_{n}^{4},$ if $n$ is even,

where $L_{n}$ and $F_{n}$ are the Lucas and the Fibonacci numbers
respectively.

###  7.2 Graph $Y(n,1,1,2)$

The number $\tau(n)=\tau_{1,1,2}(n)$ of spanning trees in the graph
$Y(n,1,1,2)$ is given by the formula

$\tau(n)={4n\,3^{n-1}}\left|\left(T_{n}({3\over
2})-1\right)\left(T_{n}({1+\sqrt{193}\over
12})-1\right)\left(T_{n}({1-\sqrt{193}\over 12})-1\right)\right|.$

By Theorem 4, $\tau_{1,1,2}(n)\sim\frac{n}{6}A_{1,1,2}^{n},\,n\to\infty,$
where

$A_{1,1,2}=\frac{1}{4}(3+\sqrt{5})(8+\sqrt{3}+\sqrt{31+16\sqrt{3}})=22.7697\ldots.$

###  7.3 Graph $Y(n,1,2,2)$

We have the following formulas for number $\tau(n)=\tau_{1,2,2}(n)$ of
spanning trees in the graph $Y(n,1,2,2).$

$\tau(n)=n\,3^{n-2}\left((\frac{1+\sqrt{13}}{2})^{n}+(\frac{1+\sqrt{13}}{2})^{-n}-2\right)\left((\frac{1-\sqrt{13}}{2})^{n}+(\frac{1-\sqrt{13}}{2})^{-n}-2\right)$

$\times\left((\frac{1+\sqrt{5}}{2})^{n}+(\frac{1+\sqrt{5}}{2})^{-n}-2\right)\left((\frac{-1-\sqrt{5}}{2})^{n}+(\frac{-1-\sqrt{5}}{2})^{-n}-2\right).$

Also, by Theorem 4,
$\tau_{1,2,2}(n)\sim\frac{n}{9}A_{1,2,2}^{n},\,n\to\infty,$ where
$A_{1,2,2}=\frac{9}{2}(3+\sqrt{5})=23.5623\ldots.$

One can show that there exists an integer sequence $a(n)$ such that
$\tau(n)=na(n)^{2}.$

##  8 Final Remarks

Theorem 1 is the first step to understand the structure of the Jacobian for
$Y(n;k,l,m).$ Also, it gives a way for calculations of
$\textrm{Jac}(Y(n;k,l,m)$ for small values of $n,k,l$ and $m.$ Theorem 2
completely describes Jacobian for $Y(n;1,1,1).$ Theorems 3 and 4 contain
convenient formulas for counting the number of spanning trees and their
asymptotics.

##  9 Acknowledgment

The first author was supported by the Basic Science Research Program through
the National Research Foundation of Korea (NRF) funded by the Ministry of
Education (2018R1D1A1B05048450). The second and the third authors were
supported by the Mathematical Center in Akademgorodok under agreement No.
075-15-2019-1613 with the Ministry of Science and Higher Education of the
Russian Federation.

Young Soo Kwon

Department of Mathematics,

Yeungnam University,

Gyeongsan, Gyeongbuk 38541, Korea

<EMAIL_ADDRESS>
Aleksandr Dmitrievich Mednykh

Sobolev Institute of Mathematics,

pr-t Acad. Koptyug, 4,

630090, Novosibirsk, Russia

Novosibirsk State University,

Pirogova str., 1,

630090, Novosibirsk, Russia

<EMAIL_ADDRESS>
Ilya Aleksandrovich Mednykh

Sobolev Institute of Mathematics,

pr-t Acad. Koptyug, 4,

630090, Novosibirsk, Russia

Novosibirsk State University,

Pirogova str., 1,

630090, Novosibirsk, Russia

<EMAIL_ADDRESS>
## References

  * [1] R. Cori, D. Rossin, On the sandpile group of dual graphs, European J. Combin., 21:4 (2000), 447–459. Zbl 0969.05034
  * [2] M. Baker, S. Norine, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Notes. 15 (2009), 2914–2955. Zbl 1178.05031
  * [3] N.L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Comb., 9:1 (1999), 25–45. Zbl 0919.05027
  * [4] R. Bacher, P. de la Harpe, 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. Zbl 0891.05062
  * [5] F.T. Boesch, H. Prodinger, Spanning tree formulas and Chebyshev polynomials, Graphs Combin., 2:1 (1986), 191–200. Zbl 0651.05028
  * [6] S.D. Nikolopoulos, C. Papadopoulos, The number of spanning trees in $K_{n}$-complements of quasi-threshold graphs, Graph Combin., 20 (2004), 383–397. Zbl 1054.05058
  * [7] R. Shrock, F.Y. Wu, Spanning trees on graphs and lattices in d-dimensions, J. Phys. A, 33 (2000), 3881–3902. Zbl 0949.05041
  * [8] S.C. Chang, L.C. Chen, W.S. Yang, Spanning trees on the Sierpinski gasket, J. Stat. Phys., 126 (2007), 649–667.Zbl 1110.82007
  * [9] D. D’Angeli, A. Donno, Weighted spanning trees on some self-similar graphs, Electron. J. Comb., 181 (2011), 16–43. Zbl 1229.05014
  * [10] W. Sun, S. Wang, J. Zhang, Counting spanning trees in prism and anti-prism graphs, J. Appl. Anal. Comput., 6 (2016), 65–75. Zbl 1463.05287
  * [11] D. Lorenzini, Smith normal form and Laplacians, J. Combin. Theory Ser. B., 98:6 (2008), 1271–1300. Zbl 1175.05088
  * [12] Yaoping Hou, Chingwah Woo, Pingge Chen, On the sandpile group of the square cycle, Linear Algebra Appl., 418 (2006), 457–467. Zbl 1108.05062
  * [13] Chen Pingge, Hou Yaoping, On the critical group of the Mobius ladder graph, Austral. J. Combin., 36 (2006), 133–142. Zbl 1104.05032
  * [14] I.A. Mednykh, M.A. Zindinova, On the structure of Picard group for Moebius ladder, Sib. Electron. Math. Rep., 8 (2011), 54–61. Zbl 1329.05147
  * [15] A.D. Mednykh, I.A. Mednykh, On the structure of the Jacobian group for circulant graphs, Dokl. Math., 94:1 (2016), 445–449. Zbl 1350.05061
  * [16] Zhang Yuanping, Yong Xuerong, M.J. Golin, The number of spanning trees in circulant graphs, Discrete. Math., 223:1 (2000), 337–350. Zbl 0969.05036
  * [17] Zhang Yuanping, Xuerong Yong, M.J. Golin, Chebyshev polynomials and spanning tree formulas for circulant and related graphs, Discrete Math., 298:1 (2005), 334–364. Zbl 1070.05029
  * [18] Chen Xiebin, Qiuying Lin, Fuji Zhang, The number of spanning trees in odd valent circulant graphs, Discrete Math., 282:1 (2004), 69–79. Zbl 1042.05051
  * [19] A. Mednykh, I. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, Discrete Math., 342:6 (2019), 1772–1781. Zbl 1414.05080
  * [20] A.D. Mednykh, I.A. Mednykh, Asymptotics and Arithmetical Properties of Complexity for Circulant Graphs, Dokl. Math., 97:2 (2018), 147–151. Zbl 1391.05150
  * [21] Y.S. Kwon, A.D. Mednykh, I.A. Mednykh, Complexity of the circulant foliation over a graph, J. Algebraic Comb., 53 (2021), 115–129. Zbl 1464.05194
  * [22] Y.S. Kwon, A.D. Mednykh, 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. Zbl 1365.05135
  * [23] I.A. Mednykh, On Jacobian group and complexity of the $I$-graph $I(n,k,l)$ through Chebyshev polynomials, Ars Math. Contemp., 15 (2018), 467–485. Zbl 1411.05126
  * [24] N.L. Biggs, Three remarkable graphs, Canad. J. Math., 25 (1973), 397–411. Zbl 0256.05114
  * [25] J.D. Horton, I.Z. Bouwer, Symmetric Y-graphs and H-graphs, J. Comb. Theory. Ser. B, 53 (1991), 114–129. Zbl 0689.05046
  * [26] P.J. Davis, Circulant Matrices, AMS Chelsea Publishing, 1994. Zbl 0418.15017
  * [27] H. Corrales, C.E. Valencia, On the critical group of matrices, Bull. Math. Soc. Sci. Math. Roumanie, 54(102):3 (2011), 213–236. Zbl 1249.05183
  * [28] G. Everest, T. Ward, Heights of polynomials and entropy in algebraic dynamics, Springer Science & Business Media, 2013. Zbl 0919.11064