| Russian Mathematical Surveys |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians A. D. Mednykhab, I. A. Mednykhab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences b Novosibirsk State University
Bibliographic databases:
    1. IntroductionThe purpose of this survey is to describe invariants of cyclic coverings of graphs. The covered graph is assumed to be fixed, and the cyclic covering group has an arbitrarily large order. A classical example of such a covering is a circulant graph. It covers a one-vertex graph with a prescribed number of loops. More sophisticated objects representing the family of cyclic coverings include $I$-, $Y$-, and $H$-graphs, generalized Petersen graphs, sandwich-graphs, discrete tori, and many others. In this survey we present analytic formulae for counting rooted spanning forests and trees in cyclic coverings, find their asymptotics and study the arithmetic properties of these quantities. Moreover, in the case of circulant graphs we give exact formulae for computing the Kirchhoff index and show that, up to an exponentially small remainder, they are specified by polynomials of degree 3. All these invariants are spectral invariants, which means that their values are determined by the spectrum of the Laplacian matrix. Of special interest are the Jacobians of graphs, which we treat as discrete versions of the Jacobians of Riemann surfaces. The Jacobian of a graph can be defined as the maximal Abelian group generated by the flows on the graph satisfying Kirchhoff’s first and second laws. According to Kirchhoff’s classical theorem, the order of this group coincides with the number of spanning trees in this graph. This group, which is also referred to as the sandpile group, the Picard group, the critical group, the dollar group, or the group of components, was independently introduced by many authors. An important specific feature of the graph Jacobian is that it has a non-spectral nature. There exist graphs with the same spectrum but different Jacobians. At the same time, there exist graphs with the same Jacobian, but different spectra. In this survey we present structural formulae for the computation of the Jacobians of circulant graphs and their simplest analogues. The basic technique for the computation of all invariants mentioned above deals with Chebyshev polynomials and their properties. 2. Main definitionsFor the sake of the reader’s convenience, in this section we define cyclic coverings of graphs and describe their main invariants. The main attention is paid to spectral invariants of graphs such as the number of spanning trees, the number of rooted spanning forests, and the Kirchhoff index. In addition, we formulate structural theorems for the computation of the Jacobian of a graph, which is in general not a spectral invariant. 2.1. The basic notion of a graph. Spanning forests and treesIn the framework of this survey a graph $G$ is an undirected finite multigraph with loops. For convenience it is assumed that each edge, including loops, is directed both possible ways. Denote by $V(G)$ and $E(G)$ its vertex set and edge set, respectively. A tree is a connected graph with no cycles. A disjoint union of trees is called a forest. A rooted tree is a tree with one distinguished vertex (the root). A forest that consists of rooted trees is called a rooted forest. A spanning tree in a connected graph $G$ is a subgraph of $G$ that is a tree containing all the vertices of $G$. A spanning forest in a graph $G$ is a subgraph of $G$ that is a forest containing all the vertices of $G$. 2.2. The Laplacian matrix of a graph and its spectral propertiesConsider a finite graph $G$ which can have multiple edges, but no loops. The matrix $A=A(G)=(a_{u,v})_{u,v\in V(G)}$, where $a_{u,v}$ is the number of edges joining the vertices $u$ and $v$, is called the incidence matrix of $G$. Denote by $d(v)$ the degree of the vertex $v\in V(G)$, and consider the diagonal matrix $D=D(G)$ with entries $d_{v,v}=d(v)$. The matrix $L=L(G)=D(G)-A(G)$ is called the Laplacian matrix or the Laplacian of the graph $G$. Note that the Laplacian matrix is always singular and non-negative definite. The number of zero eigenvalues of this matrix equals the number of connected components of the graph. In particular, the Laplacian matrix of a connected graph has exactly one zero eigenvalue, while all of its other eigenvalues are positive [70]. For more general reasoning we need to extend the concept of the Laplacian matrix of a graph. Let $X=\{x_v,v\in V(G)\}$ be the set of independent variables, and let $D(X)$ be the diagonal matrix with diagonal entries $x_v$, $v\in V(G)$. We define the generalized Laplacian matrix of the graph $G$ by $L(G,X)=D(X)-A(G)$. 2.3. Kirchhoff’s theorem on the number of spanning treesOne of the main invariants of a graph is its complexity defined as the number of spanning trees in the graph. If the graph is not connected, then it has zero complexity. The complexity of a connected graph is described by the classical Kirchhoff theorem [45], which states that its is equal to the product of all the non-zero eigenvalues of the Laplacian matrix of the graph divided by the number of graph vertices. This quantity can also be computed as the determinant of an arbitrary principal minor of the Laplacian matrix. Since Kirchhoff’s days, a lot of works devoted to investigations of the complexity of various graph properties have been published (see, for example, [88], [77], [78], [36], [85], [11], and [10]). 2.4. The Kelmans–Chelnokov theorem and the number of rooted spanning forestsAlong with the problem of finding the number of spanning trees, of special interest is the problem of counting the rooted spanning forests in a given graph. Consider a graph $G$ on $n$ vertices, and let be the characteristic polynomial of the Laplacian matrix $L(G)$. We represent this polynomial in the form
$$
\begin{equation*}
\chi_{G}(\lambda)=\lambda^n+c_{n-1}\lambda^{n-1}+\cdots+c_1\lambda.
\end{equation*}
\notag
$$
According to the main result of [44], the quantity $|c_k|$ coincides with the number of the rooted spanning forests in $G$ that consist of $k$ trees. Since all eigenvalues of the Laplacian matrix $L(G)$ are non-negative, the sequence of coefficients $c_1,c_2,\dots,c_{n-1},c_{n}$ with $c_{n}=1$ is alternating. Hence we have the following formula for the number of rooted spanning forests in $G$:
$$
\begin{equation}
\begin{aligned} \, f(G)&=f_{1}+f_{2}+f_{3}+\cdots+f_{n}= |c_{1}-c_{2}+c_{3}-\cdots+(-1)^{n-1}c_{n}| \notag \\ &=(-1)^{n}\chi_{G}(-1)=\det(I_{n}+L(G)). \end{aligned}
\end{equation}
\tag{1}
$$
This result was independently obtained by the authors of [16], [47], [32] and others. At the same time, there is very little to say about analytic formulae for the number of spanning forests. Namely, Chebotarev [14] compiled a list of rooted spanning forests in paths and cyclic graphs, and Knill [47] proved that the number of rooted spanning forests in a complete graph $K_n$ on $n$ vertices equals $(n+1)^{n-1}$. Rooted spanning forests of complete bipartite graphs were enumerated in [42]. Explicit formulae for the number of rooted spanning forests in cyclic graphs, stars, and some other graphs were presented in [47]. As for the number of unrooted forests, it is usually expressed by much more complicated formulae [13], [53], [86]. 2.5. The Kirchhoff indexLet $G$ be a connected finite graph on $n$ vertices. Denote the Laplacian matrix of $G$ by $L(G)$. It is known [70] that if the graph is connected, then all eigenvalues of $L(G)$, except perhaps one eigenvalue equal to zero, are positive. In other words, the spectrum of the Laplacian matrix of the graph $G$ has the form $0=\lambda_{0}<\lambda_{1}\leqslant\cdots\leqslant\lambda_{n-1}$. The Kirchhoff index of the graph $G$ was originally introduced by Klein and Randić [46] as the total resistance distance between its vertices. Recall the corresponding definition. Let the vertices of $G$ be labelled by the integers $1,2,\dots,n$, and suppose that each edge of $G$ is assigned a unit resistor. Then the resistance distance between two vertices $i$ and $j$, denoted by $r_{i,j}=r_{i,j}(G)$, is defined as the effective resistance between them. Following [46], we define the Kirchhoff index of the graph $G$ as the quantity
$$
\begin{equation*}
\operatorname{Kf}(G)=\sum_{1\leqslant i<j\leqslant n}r_{i,j}.
\end{equation*}
\notag
$$
This definition was motivated by the well-known Wiener index [89], defined by where $d_{i,j}$ denotes the distance between the vertices $i$ and $j$. Klein and Randić [46] showed that $\operatorname{Kf}(G)\leqslant W(G)$, where the inequality is satisfied as equality if and only if the graph $G$ is a tree. An interesting interrelation between the Kirchhoff index and the spectrum of the Laplacian matrix was independently established in [34] and [95]. The following formula is valid:
$$
\begin{equation}
\operatorname{Kf}(G)=n\sum_{j=1}^{n-1}\frac{1}{\lambda_j}\,.
\end{equation}
\tag{2}
$$
The values of the Kirchhoff index for various families of graphs were studied in [56], [73], [92], [91], [57], [19], [43], and [5]. 2.6. Mahler measureIn recent decades the asymptotic behaviour of the graph complexity was investigated from the standpoint of Mahler measure [35], [80], [81]. The general properties of the Mahler measure were presented in [82] and in [26]. It is notable that the Mahler measure is intimately related to the growth of groups, values of hypergeometric functions, and the volumes of hyperbolic manifolds [12]. Let us present the main definitions. Consider a polynomial
$$
\begin{equation*}
P(z)=a_{0}z^{s}+\cdots+a_{s-1}z+a_{s}= a_{0}\prod_{i=1}^{s}(z-\alpha_i),\qquad a_{0}\ne0,
\end{equation*}
\notag
$$
with complex coefficients. Following [58], we define its Mahler measure by
$$
\begin{equation}
M(P)=\exp\biggl(\int_{0}^{1}\log|P(e^{2\pi\mathtt{i}t})|\,dt\biggr),
\end{equation}
\tag{3}
$$
which is the geometric mean of $|P(z)|$ on the unit circle $|z|=1$. It should be noted that the quantity $M(P)$ appeared earlier in the paper [52] by Lehmer in an alternative form: The equivalence of the two definitions follows immediately from Jensen’s formula [41]
$$
\begin{equation*}
\int_{0}^{1}\log|e^{2\pi\mathtt{i}t}-\alpha|\,dt=\log_{+}|\alpha|,
\end{equation*}
\notag
$$
where $\log_{+}x$ denotes $\max(0,\log x)$. Sometimes it is more convenient to deal with the small Mahler measure, which is defined by
$$
\begin{equation*}
m(P):=\log M(P)=\int_{0}^{1}\log|P(e^{2\pi\mathtt{i}t})|\,dt.
\end{equation*}
\notag
$$
The concept of the Mahler measure can naturally be extended to the class of Laurent polynomials
$$
\begin{equation*}
R(z)=a_{s}z^{p}+a_{s-1}z^{p+1}+\cdots+a_{1}z^{p+s-1}+a_{0}z^{p+s}= a_{0}z^{p}\prod_{i=1}^{s}(z-\alpha_i),
\end{equation*}
\notag
$$
where $a_{0},a_{s}\ne0$ and $p$ is an arbitrary integer. 2.7. JacobiansThe graph invariants considered above (complexity, the number of rooted forests, and the Kirchhoff index) are spectral invariants. In other words, they depend on the eigenvalues of the Laplacian matrix. However, there exist invariants which do not depend on the spectrum of the Laplacian matrix. A typical example of such an invariant is the graph Jacobian (the Jacobian group of the graph). This group is also referred to as the Picard group, the critical group, the dollar group, or the sandpile group. This concept was independently introduced by many authors in recent decades [24], [22], [6], [9], [4], [48]. First it appeared in statistical physics in the study of the Abelian sandpile model [24]. Subsequently, it was also discovered as an efficient tool for finding stable financial configurations in the banking system [9]. This concept also arises as a discrete version of the notion of Jacobian in the classical theory of Riemann surfaces [6]. A number-theoretic approach to this concept was presented in [4]. Some aspects of this theory were considered in [48] from the standpoint of mathematical crystallography. In giving the definition of the Jacobian $\operatorname{Jac}(G)$ of a graph $G$ we follow [54]. Consider the Laplacian matrix $L(G)$ as a homomorphism $\mathbb{Z}^{|V|}\to\mathbb{Z}^{|V|}$, where $|V|=|V(G)|$ is the number of vertices in the graph $G$. Its cokernel
$$
\begin{equation*}
\operatorname{coker}(L(G))=\mathbb{Z}^{|V|}/\operatorname{im}(L(G))
\end{equation*}
\notag
$$
is an Abelian group. Let
$$
\begin{equation*}
\operatorname{coker}(L(G))\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}} \oplus\cdots\oplus\mathbb{Z}_{d_{|V|}}
\end{equation*}
\notag
$$
be its Smith normal form, which is uniquely determined by the conditions $d_i\mid d_{i+1}$, $1\leqslant i\leqslant|V|-1$. If the graph $G$ is connected, then the groups ${\mathbb Z}_{d_{1}},{\mathbb Z}_{d_{2}},\dots,{\mathbb Z}_{d_{|V|-1}}$ are finite and $\mathbb{Z}_{d_{|V|}}=\mathbb{Z}$. Define the Jacobian group (or just Jacobian) of the graph $G$ as the torsion subgroup of the cokernel $\operatorname{coker}(L(G))$. In other words,
$$
\begin{equation*}
\operatorname{Jac}(G)\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}} \oplus\cdots\oplus\mathbb{Z}_{d_{|V|-1}}.
\end{equation*}
\notag
$$
The Jacobian group is an important algebraic invariant of a finite graph. In particular, its order coincides with the number of spanning trees in the graph. At the same time, the structure of the Jacobian is known only in some special cases [40], [22], [9], [54]. The structure of the Jacobian for circulant graphs, $I$-graphs, and generalized Petersen graphs was studied in [49], [60], and [68]. Recall that the class of graphs mentioned above is rather wide; it includes cyclic graphs, complete graphs, Möbius ladders, antiprism graphs, and some other graphs. For simplest infinite families of graphs the Jacobian group was described explicitly, whereas in the general case we present a more efficient method for its description. Note that in many cases the number of spanning trees in graphs, as well as the structure of the Jacobian, can be expressed in terms of Chebyshev polynomials. There is an important observation about the structure of the Jacobian group. The order of the Jacobian as an Abelian group coincides with the graph complexity. In other words, the order of the Jacobian is a spectral characteristic of the graph. At the same time, there exist graphs which have the same spectrum of the Laplacian matrix, but non-isomorphic Jacobians [4]. 3. Cyclic coverings of graphs3.1. General definition of a cyclic covering of a graphLet there be two graphs $G=(V(G),E(G))$ and $H=(V(H),E(H))$. A surjective mapping $f\colon V(G)\to V(H)$ is called a covering mapping from $G$ to $H$ (or just a covering) if for any vertex $v\in V(G)$ the restriction of $f$ to the set of neighbours of $v$ is a bijective mapping to the neighbourhood of the vertex $f(v)$ in $H$. Recall that the neighbourhood of a vertex $v$ in a graph $G$ is the subgraph induced by $v$ and all its neighbours (adjacent vertices) in $G$ (see [27], § 6.8). The covering group of a covering $f$ consists of all automorphisms $g$ of $G$ preserving the projection, which means that $f\circ g=f$. An $n$-fold covering is said to be cyclic if the covering group is a cyclic group of order $n$. There exist several approaches to the description of cyclic coverings of graphs: the topological approach is based on the theory of covering spaces [59], the geometric approach is based on the theory of uniformization [7], and the algebraic approach is based on the theory of voltage assignment [30]. In the case where the graph $G$ has a cyclic group of automorphisms $\mathbb{Z}_n$ acting without fixed points on the vertex set and on the set of undirected edges of the graph, a cyclic covering arises as a natural projection $G\to G/\mathbb{Z}_n$. 3.2. Circulant graphs and their spectraThe simplest examples of cyclic coverings of graphs are circulant graphs. These are cyclic coverings over one-vertex graphs with a fixed number of loops. They can also be defined as the Cayley graphs of cyclic groups [21]. However, it is convenient for us to use the following equivalent definition. Let $n>1$ be a positive integer. Consider a finite tuple of integers $s_1,s_2,\dots,s_k$ such that $1\leqslant s_1<s_2<\cdots<s_k\leqslant n/2$. Define the circulant graph $G=C_{n}(s_1,s_2,\dots,s_k)$ as the graph on $n$ vertices $0,1,2,\dots,{n-1}$ in which each vertex $i$, $0\leqslant i\leqslant n-1$, is adjacent to the vertices $i\pm s_1,i\pm s_2,\dots,i\pm s_k$ $(\bmod \ n)$. The integers $s_1,s_2,\dots,s_k$ are called jumps of the graph $G$. In the case where $s_k<n/2$ all vertices of $G$ have even degree $2k$. If $n$ is even and $s_k=n/2$, then all vertices of $G$ have odd degree $2k- 1$. It is well known that $C_n(s_1,s_2,\dots,s_k)$ is connected if and only if $\operatorname{gcd}(s_1,s_2,\dots,s_k,n)= 1$. In the general case the number of connected components of $C_n(s_1,s_2,\dots,s_k)$ equals $d=\operatorname{gcd}(s_1,s_2,\dots,s_k,n)$, all vertices $0,1,\dots,d-1$ lie in different connected components, and each connected component is isomorphic to the graph $C_{n/d}(s_1/d,s_2/d,\dots,s_k/d)$. If $d>1$, then the graph $G$ is disconnected and has no spanning trees, but has spanning forests. In what follows, unless otherwise indicated, all graphs are assumed to be connected. Two circulant graphs $C_{n}(s_1,s_2,\dots,s_k)$ and $C_{n}(\tilde{s}_1,\tilde{s}_2,\dots,\tilde{s}_k)$ are said to be conjugate if there exists an integer $r$ coprime to $n$ such that the tuples $\{\tilde{s}_1,\tilde{s}_2,\dots,\tilde{s}_k\}$ and $\{rs_1,rs_2,\dots,rs_k\}$ coincide as subsets of the cyclic group $\mathbb{Z}_n$. In this case the graphs are isomorphic, with multiplication by $r$ $(\bmod \ n)$ giving an isomorphism. In 1967 Ádám conjectured that two circulant graphs are isomorphic if and only if they are conjugate [3]. The original goal of that conjecture was to give a classification of circulant graphs up to isomorphism. However, Ádám’s conjecture has turned out to be wrong. A counterexample is given by the two graphs $C_{16}(1,2,7)$ and $C_{16}(2,3,5)$. These graphs are isomorphic, but not conjugate by a multiplier [21]. A complete solution of the isomorphism problem for circulant graphs was given by Muzychuk [71]. Evdokimov and Ponomarenko [25] showed that circulant graphs can be recognized in polynomial time in the set of all graphs. A circulant matrix is a matrix of the following form:
$$
\begin{equation*}
\begin{pmatrix} a_0 & a_1 & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_0 & a_1 & \dots & a_{n-2} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_1 & a_2 & a_3 & \dots & a_0 \\ \end{pmatrix}.
\end{equation*}
\notag
$$
A matrix of this type is denoted by $\operatorname{circ}(a_0,a_1,\dots,a_{n-1})$. It is easily seen that the adjacency matrix and Laplacian matrix of a circulant graph are circulant matrices. The converse is also true: if the Laplacian matrix of a graph is circulant (for an appropriate enumeration of vertices), then the graph is circulant too. Recall [23] that the eigenvalues of the matrix $C=\operatorname{circ}(a_0,a_1,\dots,a_{n-1})$ are expressed by the following simple formulae: where $p(z)=a_0+a_1 z+\cdots+a_{n-1}z^{n-1}$ and $\varepsilon_n$ is an order $n$ primitive root of the unity. Moreover, the circulant matrix considered above can be represented in the form where $T=\operatorname{circ}(0,1,0,\dots,0)$ is the matrix representation of the shift operator
$$
\begin{equation*}
(x_0,x_1,\dots,x_{n-2},x_{n-1})\to(x_1,x_2,\dots,x_{n-1},x_0).
\end{equation*}
\notag
$$
This gives one a clue to the description of the Laplacian and its spectrum for an arbitrary circulant graph. Namely, given a circulant graph $G=C_{n}(s_1,s_2,\dots,s_k)$, consider the associated Laurent polynomial Then the Laplacian of the graph $G$ is represented in the form $L(G)=P(T)$, and its spectrum is specified by the numbers $\lambda_j=P(\varepsilon^j_n)$, $j=0,1,\dots,n-1$.3.3. Circulant foliations over graphsLet $H$ be a connected finite graph with vertices $v_1,v_2,\dots,v_m$, allowed to have multiple edges, but without loops. We denote the number of edges between vertices $v_i$ and $v_j$ by $a_{i,j}$. Since $H$ has no loops, we have $a_{i,i}=0$. To define a circulant foliation $H_n=H_n(G_1,G_2,\dots,G_m)$, to each vertex $v_i$ we assign the circulant graph $G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i})$. In the case where $G_i=C_{n}(\varnothing)$ is the empty graph on $n$ vertices, we set $k_{i}=1$ and $s_{i,1}=0$. The circulant foliation over $H$ with fibres $G_1,G_2,\dots,G_m$ is the graph with vertex set
$$
\begin{equation*}
V(H_n)=\{(k,v_i), \ k=1,2,\dots,n, \ i=1,2,\dots,m\},
\end{equation*}
\notag
$$
where for fixed $k$ the vertices $(k,v_i)$ and $(k,v_j)$ are connected by $a_{i,j}$ edges, while for fixed $i$ the vertices $(k,v_i)$, $k=1,2,\dots,n$, form a circulant graph $C_n(s_{i,1},s_{i,2},\dots, s_{i,k_i})$ in which the vertex $(k,v_i)$ is adjacent to the vertices
$$
\begin{equation*}
(k\pm s_{i,1},v_i),\ (k\pm s_{i,2},v_i),\ \dots,\ (k\pm s_{i,k_i},v_i) \pmod{n}.
\end{equation*}
\notag
$$
In what follows we refer to $H$ as the base graph, or just the base for the circulant foliation $H_{n}$. An important point in this definition is that it allows for fibres formed by empty circulant graphs $C_{n}(\varnothing)$, that is, the graphs consisting of $n$ isolated vertices. This feature extends the class of objects under study significantly and, in particular, allows one to consider $Y$- and $H$-graphs and their generalizations. Let us mention some properties of circulant foliations. There exists a projection $\varphi\colon H_n\to H$ sending the vertices $(k,v_i)$, $k=1,\dots,n$, to the vertex $v_i$, and sending bijectively the edges between two vertices $(k,v_i)$ and $(k,v_j)$, $i\ne j$, to the edges between the vertices $v_i$ and $v_j$. For each vertex $v_i$ of the graph $H$ we have $\varphi^{-1}(v_i)= G_i$, $i=1,2,\dots,m$. This mapping, being convenient from the topological and combinatorial standpoints, is in general not a graph covering. To specify the covering consider the action of the cyclic group $\mathbb{Z}_n$ on the graph $H_n$ defined by $(k,v_{i})\to(k+1,v_{i})$, $k\pmod{n}$. Then $\mathbb{Z}_n$ acts without fixed points on the set of vertices and directed edges of the graph, and the quotient graph $H_{n}/\mathbb{Z}_{n}$ is an equipped graph $\widehat{H}$ obtained from $H$ by attaching $k_i$ loops to each $i$th vertex of $H$. Thus, $H_n$ is an $n$-fold cyclic covering over the equipped graph $\widehat{H}$. 3.4. Families of circulant foliations: $I$-, $Y$-, $H$-graphs and discrete toriIn this subsection we give a description of several families of circulant foliations, which are cyclic coverings over simplest graphs. First we consider the sandwich graph $\operatorname{SW}_n=H_n(G_1,G_2,\dots,G_m)$ formed by the circulant graphs $G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i})$, $i=1,2,\dots,m$. To create $\operatorname{SW}_n$, we take the base graph $H$ to be a path graph on $m$ vertices $v_1,v_2,\dots,v_m$ with endpoints $v_1$ and $v_m$. An important particular case of this construction is the $I$-graph $I(n,k,l)$ which occurs by taking $m=2$ and has two cyclic fibres $G_1=C_n(k)$ and $G_2=C_n(l)$. Also, the generalized Petersen graph $\operatorname{GP}(n,k)$ is an $I$-graph with parameters $n,k$, and $l=1$ [83]. The sandwich $H_n(G_1,G_2)$ of arbitrary two circulant graphs $G_1$ and $G_2$ was considered in [2]. For the second example, we consider the family of generalized $Y$-graphs $Y_n=Y_n(G_1,G_2,G_3)$. To construct such a graph we take the base graph $H$ to be a $Y$-shaped graph consisting of four vertices $v_1$, $v_2$, $v_3$, and $v_4$ and three edges $v_1v_4$, $v_2v_4$, and $v_3v_4$. To degree 1 vertices of $H$ we assign circulant graphs $G_1$, $G_2$, and $G_3$, and to its central vertex we assign the empty circulant graph $G_4=C_n(\varnothing)$. Then, according to the definition of circulant foliations, we put $Y_n=H_n(G_1,G_2,G_3,G_4)$. In the particular case where $G_1=C_n(k)$, $G_2=C_n(l)$, and $G_3=C_n(m)$, we obtain the $3$-regular $Y$-graph $Y(n;k,l,m)$, which was defined earlier in [8] and [37]. One more example is the generalized $H$-graph $H_n(G_1,G_2,G_3,G_4,G_5,G_6)$, where $G_1$, $G_2$, $G_3$, and $G_4$ are arbitrary circulant graphs and $G_5=G_6=C_n(\varnothing)$ are the empty graphs on $n$ vertices. In this case we take the base graph $H$ to be the graph with vertices $v_1$, $v_2$, $v_3$, $v_4$, $v_5$, and $v_6$ and edges $v_1v_5$, $v_5v_3$, $v_2v_6$, $v_6v_4$, and $v_5v_6$. In the case where $G_1=C_n(i)$, $G_2=C_n(j)$, $G_3=C_n(k)$, and $G_4=C_n(l)$ we obtain the $3$-regular graph $H(n;i,j,k,l)$, which was investigated in [37]. For the sake of simplicity we will use the notation $H_n(G_1,G_2,G_3,G_4)$, ignoring the last two empty graph entries. A discrete torus graph is the Cartesian product of the cyclic graphs $C_n$ and $C_m$. We can also consider it as a circulant foliation
$$
\begin{equation*}
T_{n,m}=H_{n}(\,\underbrace{C_{n}(1),\dots,C_{n}(1)}_{m \text{ times }}\,)
\end{equation*}
\notag
$$
with the base $H=C_{m}(1)$ and $m$ identical fibres $C_{n}(1),\dots,C_{n}(1)$. 3.5. Cyclic covering of general formLet $H$ be a finite connected graph with vertices $v_1,v_2,\dots,v_r$ (allowed to have loops and multiplie edges). To describe the general construction of an $n$-fold cyclic covering of the graph $H$, consider the cyclic group $\Gamma=\langle\mathbb{Z}_n,+\rangle$ of residue classes modulo $n$. For convenience it will be assumed that all edges of $H$, including loops, are directed both possible ways. For any directed edge $e$ of $H$ the oppositely directed edge is denoted by $\bar{e}$. Making use of the voltage assignment technique developed in [30], to each directed edge $e$ of the graph $H$ we assign a voltage $\alpha(e)$, namely, an element of $\Gamma$. We follow the rule that the sum of the voltages assigned to two oppositely directed edges is zero: $\alpha(e)+\alpha(\bar{e})=0$. For any $i,j=1,\dots,r$ and any $k=1,\dots,a_{i,j}$ we denote the voltage of the $k$th directed edge from $v_i$ to $v_j$ by $\alpha_k(i,j)$. For distinct $i$ and $j$ we assume that $\alpha_k(j,i)=-\alpha_k(i,j)$. Since each loop is directed in two opposite ways, one can take the voltage $\alpha_k(i,i)$ for one of the directions (arbitrarily chosen) and $-\alpha_k(i,i)$ for the other. Consider the $n$-fold cyclic covering $H_n=H_{n}(\alpha)$ of the graph $H$ derived by the voltage assignment $\alpha=\{\alpha_k(i,j)$, $i,j=1,\dots,r$, $k=1,\dots,a_{i,j}\}$. According to the general voltage theory [30], the graph $H_{n}$ has the vertex set $u_{i,s}$, $i=\!1,2,\dots,r$, $s\kern-1pt=\!1,2,\dots,n$, and the edge set $v_{i,s}v_{j,s+\alpha_k(i,j)}$, where $i,j\kern-1pt=\kern-1pt 1,2,\dots,r$, $k=\!1,2,\dots,a_{i,j}$, and the second indices are taken modulo $n$. It should be noted that all $n$-fold cyclic coverings of the graph $H$ can be obtained in such a way. In particular, this construction covers circulant graphs, Haar graphs, circulant foliations, and many other families of graphs. 4. Circulant graphs with even number of jumps4.1. A theorem on the number of spanning treesIn this subsection we present analytic formulae for the number of spanning trees in circulant graphs $C_{n}(s_1, s_2,\dots,s_k)$ with vertices of even degree. The results below were obtained by the authors of this work; they were published in [61] and [62]. It should be noted that some results close in spirit were previously obtained in [93], [18], and [94]. The approach taken below seems to be more convenient and simple. It allows one to derive formulae for the complexity function in closed form and examine thoroughly its arithmetic properties. In addition, the explicit form of the formula obtained allows one to describe its asymptotic behaviour in terms of the geometric parameters of the graph and the Mahler measure of the associated polynomial. In the case where all vertices of the graph have even degrees the following theorem is valid ([62], Theorem 1 and Corollary 1). Theorem 4.1. The number $\tau(n)$ of spanning trees in a circulant graph is given by the formula Here $q=s_1^2+s_2^2+\cdots+s_k^2$ and the $w_p$, $p=1,2,\dots,s_k-1$, are all the roots of the algebraic equation where $Q(w)=\sum_{j=1}^k(T_{s_j}(w)-1)$ and $T_k(w)$ is a Chebyshev polynomial of the first kind. 4.2. An asymptotic formula for the number of spanning treesConsider the infinite family of graphs $G_n$, $n\in \mathbb{N}$, and denote by $\tau(n)=\tau(G_n)$ the number of spanning trees in the graph $G_n$. In many cases it is important to know the asymptotic behaviour of the function $\tau(n)$. Denote the number of vertices of $G_n$ by $v(G_n)$. The limit (if it exists) is called the thermodynamic limit (as well as the tree entropy or bulk limit) of the family $G_n$. For various families of graphs this quantity was studied in many papers on statistical physics (see, for example, [87], [90], [79], [35], and [55]).In this subsection we present asymptotic formulae for the number of spanning trees in circulant graphs, which were derived in [61] and [62]. It is interesting to compare these results to the ones in [93], [18], [94], and [55], where similar asymptotic formulae were obtained by other methods. The following result holds ([62], Theorem 2). Theorem 4.2. The number of spanning trees in a circulant graph has the following asymptotic behaviour: where $A=\exp\biggl(\displaystyle\int_{0}^{1} \log|P(e^{2\pi\mathrm{i}t})|\,dt\biggr)$ is the Mahler measure of the associated Laurent polynomial $P(z)=2k-\sum_{i=1}^k(z^{s_i}+z^{-s_i})$ and $q=s_1^2+s_2^2+\cdots+s_k^2$. Theorem 4.2 immediately yields the following result, which was previously obtained in [93] and [94]. Corollary 4.1. The thermodynamic limit of a sequence of circulant graphs $C_{n}(s_1, s_2,\dots,s_k)$ is equal to the small Mahler measure of the associated Laurent polynomial $P(z)$. In other words, where $m(P)=\displaystyle\int_0^1\log|P(e^{2\pi\mathrm{i}t})|\,dt$ and $P(z)=2k-\sum_{i=1}^k(z^{s_i}+z^{-s_i})$. 4.3. The generating function for the number of spanning trees is rationalThe following theorem was obtained in [65]; it gives an affirmative answer to the question of Lando of whether the generating function for the number of spanning trees in a circulant graph is rational. Theorem 4.3. Let $\tau(n)$ be the number of spanning trees in a circulant graph $C_{n}(s_1,s_2,\dots,s_k)$. Then is a rational function with integer coefficients. Moreover, $F(z)=F(1/z)$. Note that the radius of convergence of the series $F(z)$ is $R=1/A$, where $A$ is the Mahler measure of the associated Laurent polynomial of the graph $C_{n}(s_1, s_2,\dots,s_k)$. This follows directly from Theorem 4.2 and the Cauchy–Hadamard formula. 4.4. Arithmetic properties of the number of spanning treesIt was noted in the series of works [93], [18], [94] that in many important cases the number of spanning trees in a circulant graph is $\tau(n)=n\,a(n)^2$, where $a(n)$ is an integer sequence. However, this is not always so. For example, in the case of the graph $C_n(1,3)$ and even $n$ we have $\tau(n)=2n\,a(n)^2$ for a certain integer sequence $a(n)$. The aim of this subsection is to explain this phenomenon. Recall that each positive integer $p$ can uniquely be represented in the form $p=q\,r^2$, where $p$ and $q$ are positive integers and $q$ is square-free. We call $q$ the square-free part of the integer $p$. The following theorem holds [61], [62]. Theorem 4.4. Denote by $\tau(n)$ the number of spanning trees in a circulant graph $C_{n}(s_1,s_2,\dots,s_k )$, where $1\leqslant s_1<s_2<\cdots<s_k<n/2$. Let $p$ be the number of odd members of the sequence $s_1,s_2,\dots,s_k$ and $q$ be the square-free part of $p$. Then there exists an integer sequence $a(n)$ such that (a) $\tau(n)=n\,a(n)^2$ if $n$ is odd; (b) $\tau(n)=q \,n\,a(n)^2$ if $n$ is even. It should be noted that $p$ in Theorem 4.4 can be replaced by the maximum eigenvalue of the Laplacian matrix of the graph $C_{n}(s_1,s_2,\dots,s_k)$. As follows from [62], it equals Let us give several examples illustrating the results presented above. Example 4.1 (the graph $C_n(1,2)$). In this case $\tau(n)=nF_n^2$, where $F_n$ is the $n$th Fibonacci number, $A=(3+\sqrt{5}\,)/2$, $q=5$, and $\tau(n)\sim(n/5)A^n$ as $n\to\infty$. Moreover, Example 4.2 (the graph $C_n(1,3)$). Theorem 4.1 provides the following formula for the number of spanning trees: Further, where $w$ is the same as in the previous example. Example 4.3 (the graph $C_n(2,3)$). By Theorem 4.1 we have 4.5. The Kirchhoff index and its asymptoticThe aim of this subsection is to write out an explicit analytic formula for the Kirchhoff index of a circulant graph $C_{n}(s_{1},s_{2},\dots,s_{k})$, which was obtained in [64], and to investigate its asymptotic behaviour as $n$ tends to infinity. These formulae are presented in the form of a sum of finitely many terms (the number of terms does not depend on $n$) and the terms are rational functions evaluated at zeros of a certain explicitly given polynomial. Theorem 4.5. The Kirchhoff index of a circulant graph $G_{n}=C_{n}(s_{1},s_{2},\dots,s_{k})$ is calculated by the formula where the $w_{p}$ are the zeros of the polynomial different from 1, and $T_{n}(w)$ and $U_{n-1}(w)$ are Chebyshev polynomials of the first and second kind, respectively. As a corollary, we obtain an asymptotic formula for the behaviour of the Kirchhoff index for circulant graphs $G_{n}=C_{n}(s_{1},s_{2},\dots,s_{k})$ as $n$ tends to infinity ([64], Corollary 1). Corollary 4.2. The following asymptotic formula holds: where $P(z)=2k-\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})$, and $A=\min\{|z|\colon P(z)=0,|z|>1\}$ is a constant which depends only on $s_1,s_2,\dots,s_k$. Note that the main term in this expression is a cubic polynomial in $n$ with constant term zero. Let us consider several examples illustrating the results presented above. Example 4.5 (the graph $C_{n}(1,2)$). For this family of graphs the Kirchhoff index can be found by the formula where $F_{n}$ is the $n$th Fibonacci number. Note that where $\phi=(1+\sqrt{5}\,)/2$ is the golden ratio. Example 4.6 (the graph $C_{n}(1,3)$). The Kirchhoff index of the family of circulant graphs $C_n(1,3)$ exhibits the following asymptotic behaviour: where $A=\sqrt{\Bigl(1+\sqrt{5}+\sqrt{2(1+\sqrt{5}\,)}\,\Bigr)\Big/2}\simeq 1.700015\dots$ . 5. Circulant graphs with vertices of odd degree5.1. The number of spanning trees in graphs with vertices of odd degreeIn the case of circulant graphs with vertices of odd degree the number of spanning trees can be found in the following way ([62], Theorem 2). Theorem 5.1. Let $C_{2n}(s_1,s_2,\dots,s_k,n)$, where $1\leqslant s_1<s_2<\cdots<s_k< n$, be a circulant graph with vertices of odd degree. Then the number $\tau(n)$ of spanning trees in $C_{2n}(s_1,s_2,\dots,s_k,n)$ obeys the formula where $q=s_1^2+s_2^2+\cdots+s_k^2$ and the numbers $u_p$, $p=1,2,\dots,s_k-1$, and $v_p$, $p=1,2,\dots,s_k$, are the roots of the algebraic equations respectively. Here $Q(w)=2k+1-2\sum_{i=1}^{k}T_{s_i}(w)$, and $T_k(w)$ is a Chebyshev polynomial of the first kind. 5.2. An asymptotic formula for the number of spanning trees in graphs with vertices of odd degreeThe following two results were obtained in [62]. Theorem 5.2. Consider a circulant graph $G_n=C_{2n}(s_1,s_2,\dots,s_k,n)$, $1\leqslant s_1 < s_2 < \cdots < s_k < n$, and assume that $\operatorname{gcd}(s_1,s_2,\dots,s_k)=d$. Then the number of spanning trees in $G_n$ has the following asymptotic behaviour: Here $q=s_1^2+s_2^2+\cdots+s_k^2$ and is the Mahler measure of the Laurent polynomial $P(z)(P(z)+2)$, where $P(z)=2k-\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})$. Corollary 5.1. The thermodynamic limit of the sequence of circulant graphs $C_{2n}(s_1,s_2, \dots,s_k,n)$ is equal to the small Mahler measure of the associated Laurent polynomial $R(z)=P(z)(P(z)+2)$, where $P(z)=2k-\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})$. In other words, where $m(R)=\displaystyle\int_0^1\log|R(e^{2\pi\mathrm{i}t})|\,dt$. 5.3. Arithmetic properties of graphs with vertices of odd degreeThe following theorem describes some arithmetic properties of the number of spanning trees in circulant graphs with vertices of odd degree ([62], Theorem 3). Theorem 5.3. Let $\tau(n)$ denote the number of spanning trees in a circulant graph $C_{2n}(s_1,s_2,\dots,s_k,n)$, where $1\leqslant s_1< s_2<\cdots< s_k< n$. Let $p$ be the number of odd members of the sequence $s_1,s_2,\dots,s_k$. Let $q$ be the square-free part of the number $2p$ and $r$ be the square-free part of the number $2p+1$. Then there exists an integer sequence $a(n)$ such that (a) $\tau(n)=r\,n\,a(n)^2$ if $n$ is odd; (b) $\tau(n)=q\,n\,a(n)^2$ if $n$ is even. As follows from the proof of Theorem 4 in [62], the maximum eigenvalue $\lambda_{\max}$ of the Laplacian matrix of the graph $C_{2n}(s_1,s_2,\dots,s_k,n)$ is $4p+2$ if $n$ is odd and $4p$ if $n$ is even. This fact allows us to replace both quantities $r$ and $q$ in the statement of Theorem 5.3 with $\lambda_{\max}/2$. 5.4. Kirchhoff index for graphs with vertices of odd degreeExplicit analytic formulae for the Kirchhoff indices of circulant graphs of the form $C_{2n}(s_{1},s_{2}, \dots,s_{k},n)$ and their asymptotic behaviour as $n$ tends to infinity were presented in [64]. These formulae contain rational expressions in Chebyshev polynomials and their derivatives. Here we restrict ourselves to a particular case of this result, which was independently obtained in [19] and [5]. Let us also present a close result, which was obtained in [20] and [5] by different methods. 5.5. The generating function for the number of spanning treesThat the generating function for the number of spanning trees in the graph $C_{2n}(s_{1},s_{2},\dots, s_{k},n)$ is rational (a result similar to Theorem 4.3) was shown in [65]. 5.6. ExamplesLet us give a series of examples that illustrate the results formulated in § 5. Example 5.1 (Möbius ladder $C_{2n}(1,n)$). For this family of graphs by Theorem 5.1 we have Example 5.2 (the graph $C_{2n}(1,2,n)$). Applying Theorem 5.2 gives where $K_{1,2}=(3+\sqrt{5})(4+\sqrt{3}+\sqrt{15+8\sqrt{3}}\,)/4\approx 14.54\dots$ . Also, by Theorem 5.3, there exists an integer sequence $a(n)$ such that $\tau(n)=2n\,a(n)^2$ if $n$ is even and $\tau(n)=3n\,a(n)^2$ if $n$ is odd. 6. Circulant graphs with non-fixed jumpsIn this section we consider a special class of circulant graphs, namely, circulant graphs with non-fixed jumps. They are defined in the same way as conventional circulant graphs, but with special constraints imposed on the number of vertices and the structure of jumps. More precisely, we deal with circulant graphs
$$
\begin{equation*}
G_n=C_{\beta n}(s_1,s_2,\dots,s_k, \alpha_1n,\alpha_2n,\dots,\alpha_{\ell}n),
\end{equation*}
\notag
$$
on $\beta\,n$ vertices with jumps $s_1,s_2,\dots,s_k$, $\alpha_{1}n,\alpha_{2}n,\dots,\alpha_{\ell}n$, satisfying
$$
\begin{equation*}
1\leqslant s_1<s_2<\cdots<s_k<\biggl[\frac{\beta n}{2}\biggr]\quad\text{and}\quad 1\leqslant\alpha_1<\alpha_2<\cdots<\alpha_{\ell}\leqslant \biggl[\frac{\beta}{2}\biggr].
\end{equation*}
\notag
$$
We are interested in the study of such graphs for sufficiently large values of $n$. In what follows $s_1,s_2,\dots,s_k$, $\alpha_1,\alpha_2,\dots,\alpha_{\ell}$, and $\beta$ are assumed to be fixed positive integers. In particular, the graph $G_n$ has no multiple edges if $\alpha_{\ell}<\beta/2$. If $\alpha_{\ell}=\beta/2$, then the graph has exactly two edges between pairs of vertices $v_i$ and $v_{i+\beta\,n/2}$, where indices are taken modulo $\beta\,n$. In this case $\beta$ is definitely an even number. A typical example is the graph $C_{2n}(1,n)$, which, in accordance with the above agreement, is realized by the Möbius ladder on $2n$ vertices with double rungs. Remark 6.1. In § 5 and in the series of papers [93], [18], [61], [62] devoted to circulant graphs with vertices of odd degree the symbol $C_{2n}(1,n)$ is used to denote the Möbius ladder with simple rungs. Such a graph has vertices of odd degree equal to 3. To avoid misreading we denote the Möbius ladder with double rungs by $C''_{2n}(1,n)$. 6.1. Spanning trees in circulant graphs with non-fixed jumpsThe following result was obtained in [67]. Theorem 6.1. The number of spanning trees in a circulant graph with non-fixed jumps As a corollary of Theorem 6.1, we obtain a result presented by Louis in [55] in a slightly different form. Corollary 6.1. The number of spanning trees in a circulant graph with non-fixed jumps is given by the formula where $T_n(w)$ is a Chebyshev polynomial of the first kind. Let us present one more corollary of Theorem 6.1. Corollary 6.2. The number of spanning trees in a circulant graph with non-fixed jumps 6.2. Arithmetic properties of the number of spanning trees in circulant graphs with non-fixed jumpsThe arithmetic properties of the number of spanning trees in circulant graphs with non-fixed jumps are described in the following theorem ([67], Theorem 5.1). Theorem 6.2. Denote by $\tau(n)$ the number of spanning trees in the circulant graph where $1\leqslant s_1<s_2<\cdots<s_k<[\beta n/2]$ and $1\leqslant\alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant [\beta/2]$. Let $p$ and $q$ denote the number of odd members of the sequences $s_1,s_2,\dots,s_k$ and $\alpha_1,\alpha_2,\dots,\alpha_\ell$, respectively. Denote by $r$ the square-free part of the integer $p$ and by $s$ the square-free part of the integer $p+q$. Then there exists an integer sequence $a(n)$ such that (a) $\tau(n)=\beta\,n\,a(n)^2$ if $\beta\,n$ is odd; (b) $\tau(n)=\beta\,r\,n\,a(n)^2$ if $n$ is even; (c) $\tau(n)=\beta\,s\,n\,a(n)^2$ if $n$ is odd and $\beta$ is even. 6.3. The asymptotic behaviour of the number of spanning trees in circulant graphs with non-fixed jumpsThe following theorem describes the asymptotic behaviour of the number of spanning trees [67]. Theorem 6.3. Let $\operatorname{gcd}(s_1,s_2,\dots,s_k)=d$ and $\operatorname{gcd}(\alpha_1,\alpha_2,\dots,\alpha_\ell,\beta)=1$. Then the number of spanning trees in the circulant graph with non-fixed jumps Let us give several examples illustrating the results presented above. Example 6.1 (the graph $C''_{2n}(1,n)$ — Möbius ladder with double rungs). Using Theorem 6.1 we obtain It is interesting to compare this result with a similar result in [94] (Theorem 4). Recall [11] that the number of spanning trees in the Möbius ladder with simple rungs is $n(T_n(2)+1)$. Example 6.2 (the graph $C_{2n}(1,2,n)$). In this case we have Example 6.3 (the graph $C_{2n}(1,2,3,n)$). For this family of graphs the number of spanning trees is given by the formula where and $\omega_1$, $\omega_2$, and $\omega_3$ are the roots of the cubic equation $2w^3+w^2-w-3=0$. Also, the following arithmetic properties are valid: $\tau(n)=6n\,a(n)^2$ if $n$ is odd and $\tau(n)=4n\,a(n)^2$ if $n$ is even. Moreover, $\tau(n)\sim(n/28)A^{n}$, $n\to\infty$, where $A\approx42.4038$. Example 6.4 (the graph $C_{3n}(1,n)$). In this case we have Example 6.5 (the graph $C_{3n}(1,2,n)$). Theorem 6.1 yields the relation Example 6.6 (the graph $C_{6n}(1,n,3n)$). In the case under consideration For an appropriate integer sequence $a(n)$ we have $\tau(n)=6n\,a(n)^2$ if $n$ is even and $\tau(n)=18n\,a(n)^2$ if $n$ is odd. Example 6.7 (the graph $C_{12n}(1,3n,4n)$). In this case 7. Circulant foliations of graphs7.1. The number of spanning trees in circulant foliationsGiven an arbitrary circulant foliation where
$$
\begin{equation*}
G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i}),\qquad i=1,2,\dots,m,
\end{equation*}
\notag
$$
consider the generalized Laplacian matrix of the base graph $L(H,X)$. We define $X$ by the formula
$$
\begin{equation*}
x_{i}=2k_{i}+d_i-\sum_{j=1}^{k_i}(z^{s_{i,j}}+z^{-s_{i,j}}),
\end{equation*}
\notag
$$
where $d_i$ is the degree of the vertex $v_i$ in $H$. By the definition of a circulant graph, in the case where $G_{i}\ne C_{n}(\varnothing)$ we have $1\leqslant s_{i,1}<s_{i,2}<\cdots<s_{i,k_{i}}$. Then $x_{i}$ is a Laurent polynomial with leading term $-z^{s_{i,k_{i}}}$. If $G_{i}=C_{n}(\varnothing)$, then $x_{i}=d_{i}$. Let $P(z)=\det(L(H,\,X))$, and note that $P(z)$ is a Laurent polynomial with integer coefficients. For further resoning we need to investigate the structure of the leading term of the polynomial $P(z)$. This term is the product of the polynomials $x_{i}=2k_{i}+d_{i}- \sum_{j=1}^{k_{i}}(z^{s_{i,j}}+z^{-{s_{i,j}}})$, where $s_{i,k_{i}}>0$, and the determinant of the matrix obtained from $L(H,\,X)$ by deleting all rows and columns corresponding to non-empty circulant fibres. The leading term of $P(z)$ can be calculated with the use of the following lemma. Lemma 7.1. Let $V'=(v_1,v_2,\dots,v_{m'})$ be a (maybe empty) subset of vertices of the base graph $H$ of a circulant foliation $H_n(G_1,G_2,\dots,G_m)$ with empty circulant fibres $C_{n}(\varnothing)$. Define $H'$ to be the subgraph of $H$ induced by $V'$. Then the leading term of the polynomial $P(z)$ is given by the formula where $\eta=\det(L(H',X'))$, $s=\sum_{j=1}^{m}s_{j,k_{j}}$, $X'=(d_{1},d_{2},\dots,d_{m'})$, and $d_{j}$ is the degree of the vertex $v_j$ in $H$. Proof. By definition $P(z)=\det(L(H,X))$, where For $j=1,2,\dots,m'$ we have $x_{j}=d_{j}$, since $k_j=1$ and $s_{j,1}=0$. If $j=m'+1,\dots,m$, then the leading term of the polynomial $x_j$ in the variable $z$ is $-z^{s_{j,k_{j}}}$. As all the other entries of the matrix $L(H,X)$ are integer constants, the claim of the lemma follows from the basic properties of determinants. Note that $L(H',X')$ is a symmetric strictly diagonally dominant matrix ([50], Lemma 5.1). Hence $\eta>0$. In the case where $m'=0$ we put $\eta=1$. Consider one more specification $L(H,W)$ for the generalized Laplacian of $H$ with the set $W=(w_1,w_2,\dots,w_m)$, where $w_{i}=2k_{i}+d_i-\sum_{j=1}^{k_i}2\,T_{s_{i,j}}(w)$ and $T_l(w)=\cos(l\arccos w)$ is the Chebyshev polynomial of the first kind. Set $Q(w)=\det(L(H,\,W))$. Then $Q(w)$ is a polynomial with integer coefficients and degree $s=s_{1,k_1}+s_{2,k_2}+\cdots+s_{m,k_m}$. Since $(z^n+z^{-n})/2=T_n((z+z^{-1})/2)$, we have $P(z)=Q(w)$, where $w=(z+z^{-1})/2$. Remark 7.1. With the notation of Lemma 7.1, the leading term of the polynomial $Q(w)$ is $(-1)^{m-m'}2^{s}\eta\,w^{s}$. The number $\bar{m}=m-m'$ coincides with the number of non-degenerate fibres of the foliation $H_n$. The main result of this subsection is given by the following theorem. This is a corrected version of Theorem 4.2 in [51], whose original formulation contained a misprint. Theorem 7.1. The number $\tau(n)$ of spanning trees in a circulant foliation $H_{n}(G_1, \dots,G_m)$ is given by the formula Proof. For the reader’s convenience we present a sketch of the proof of Theorem 7.1. Using the arguments in the proof of Theorem 4.2 in [51] we obtain
$$
\begin{equation}
\tau(n)=(-1)^{(\bar{m}+s)(n-1)}n\,\eta^{n-1}\tau(H) \prod_{j=1}^{s-1}\frac{T_{n}(w_{j})-1}{w_{j}-1}\,,
\end{equation}
\tag{5}
$$
where $\bar{m}$ is the number of non-degenerate fibres in the discrete Seifert fibre space. Note that the right-hand side of (5) is positive.
Consequently,
$$
\begin{equation*}
\tau(n)=n\,\eta^{n-1}\tau(H)\prod_{j=1}^{s-1}|T_{n}(w_{j})-1| \Bigm/\prod_{j=1}^{s-1}|w_{j}-1|.
\end{equation*}
\notag
$$
By Lemma 7.1 the polynomial $Q(w)$ has leading coefficient $a_{0}$ with absolute value $2^{s}\eta$.
Moreover, by Lemma 4.1 in [51] we have $Q(1)=0$ and $Q'(1)=-2q\tau(H)$. This gives
$$
\begin{equation*}
\prod_{j=1}^{s-1}|w_{j}-1|=\frac{|Q'(1)|}{|a_{0}|}= \frac{q\,\tau(H)}{2^{s-1}\eta}\,.
\end{equation*}
\notag
$$
By making use of the relations obtained we complete the proof. 7.2. Arithmetic properties of the number of spanning trees in circulant foliationsThe following result was obtained in Theorem 5.1 in [51]. Theorem 7.2. Let $\tau(n)$ be the number of spanning trees in a circulant foliation $H_n$. Denote by $p$ the square-free part of the number $Q(-1)$. Then there exists an integer sequence $a(n)$ such that (a) $\tau(n)= n\,\tau(H)\,a(n)^{2}$ if $n$ is odd; (b) $\tau(n)=p\,n\,\tau(H)\,a(n)^{2}$ if $n$ is even. Theorem 7.2 implies the following corollary. Corollary 7.1. The number of spanning trees in a circulant foliation $H_n$ is divisible by $n\,\tau(H)$, where $\tau(H)$ is the number of spanning trees in the base graph $H$. 7.3. The asymptotic behaviour of the number of spanning trees in a circulant foliationThe main result of this subsection is the following theorem, which was proved in [51] (see [51], Theorem 6.1) under the assumption that the absolute value $\eta$ of the leading coefficient of the polynomial $P(z)$ is equal to one. However, as shown in [50], this proof also applies to an arbitrary value of $\eta$. Theorem 7.3. The asymptotic behaviour of the number $\tau(n)$ of spanning trees in the circulant foliation $H_n$ under the condition is given by the formula where $q=\sum_{i=1}^{m}\,\sum_{j=1}^{k_i}s_{i,j}^2$ and $A=\exp\biggl(\displaystyle\int_{0}^{1} \log|P(e^{2 \pi \mathtt{i} t})|\,\textrm{d}t\biggr)$ is the Mahler measure of the polynomial $P(z)$. 7.4. Examples Example 7.1 (the circulant graph $C_{n}(s_{1},s_{2},\dots,s_{k})$). Consider the graph $C_{n}(s_{1}, s_{2},\dots,s_{k})$ as a circulant foliation $H_{n}(G_{1})$ over the single-vertex graph $H=\{v_{1}\}$ with fibre $G_{1}=C_{n}(s_{1},s_{2},\dots,s_{k})$. In this case $d_{1}=0$, $L(H,X)=(x_{1})$, Example 7.2 (the $I$-graph $I(n,k,l)$ and the generalized Petersen graph $\operatorname{GP}(n,k)$). We take the base graph $H$ to be a path graph on two vertices. Let $G_{1}=C_{n}(k)$ and $G_{2}=C_{n}(l)$. Then Example 7.3 (a sandwich of $m$ circulant graphs). Consider a path graph $H$ on $m$ vertices. We call the graph $H_{n}(G_{1},G_{2},\dots,G_{m})$ the sandwich graph of the circulant graphs $G_{1},G_{2},\dots,G_{m}$. In this case $d_{1}=d_{m}=1$ and $d_{i}=2$, $i=2,\dots,m-1$. We set Example 7.4 (a generalized $Y$-graph). Consider the generalized $Y$-graph In this case where $A_{i}(w)=2k_{i}+1-\sum_{j=1}^{k_{i}}2T_{s_{i,j}}(w)$. Example 7.5 (a generalized $H$-graph). Following [51], we define the $H$-graph $H_{n}(G_{1},G_{2},G_{3},G_{4})$. Here each $G_{i}$ is the graph $C_{n}(s_{i,1},\,s_{i,2},\dots,s_{i,k_i}),\,i=1,2,3,4$. In this case where the $A_{i}(w)$ are the same as in the previous example. Example 7.6 (the discrete torus $T_{n,m}=C_n\times C_m$). The discrete torus is defined by Example 7.7 (the direct product $C_n\times H$, where $H$ is a regular graph). Let $H$ be a connected $d$-regular graph. We identify the direct product $C_n\times H$ with Let $X=(x,\dots,x)$ ($m$ times); then $L(H,X)=x I_{m}-A(H)$. This means that $\det(L(H,X))$ coincides with the characteristic polynomial $\chi_{H}(x)$ of the graph $H$. We have $Q(w)=\chi_{H}(2+d-2w)$. Then $Q(-1)=\chi_{H}(4+d)$. 8. General cyclic coverings of graphsIn this section we describe the general construction of cyclic coverings of graphs and present the main results on counting spanning trees in such coverings. Let $H$ be a finite connected graph on vertices $v_1, v_2,\dots,v_r$ which is allowed to have loops and multiple edges. The adjacency matrix of $H$ has the form
$$
\begin{equation*}
A(H)=\begin{pmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,r} \\ a_{2,1} & a_ {2,2} & \dots & a_{2,r} \\ \vdots & \vdots & \ddots & \vdots \\ a_{r, 1} & a_{r, 2} & \dots & a_{r,r} \\ \end{pmatrix},
\end{equation*}
\notag
$$
where $a_{i,j}$ is the number of edges between $v_i$ and $v_j$ if $i\ne j$, and twice the number of loops at the vertex $v_i$ if $i=j$. Consider the cyclic covering $H_n=H_{n}(\alpha)$ of the graph $H$ constructed by means of a voltage assignment $\alpha=\{\alpha_k(i,j),\,i, j=1,\dots,r,\,k=1,\dots,a_{i,j}\}$. According to the general construction described in § 3.5, the graph $H_{n}$ has the vertex set $u_{i,s}$, $i=1,2,\dots,r$, $s=1,2,\dots,n$, and the edge set $v_{i,s}v_{j,s+\alpha_k(i,j)}$, where $i,j=1,2,\dots,r$, $k=1,2,\dots,a_{i,j}$, and the second indices are taken modulo $n$. The adjacency matrix $A(H_{n})$ of $H_{n}$ is the block matrix
$$
\begin{equation*}
A(H_{n})=\begin{pmatrix} B_{1,1} & B_{1,2} & \dots & B_{1,r} \\ B_{2,1} & B_{2,2} & \dots & B_{2,r} \\ \vdots & \vdots & \ddots & \vdots \\ B_{r,1} & B_{r,2} & \dots & B_{r,r}\\ \end{pmatrix},
\end{equation*}
\notag
$$
where the $(i,j)$th block entry $B_{i,j}=B_{i,j}(n)$, $i,j=1,2,\dots,r$, is given by the formulae
$$
\begin{equation}
B_{i,j}=\sum_{k=1}^{a_{i,j}}T_{n}^{\alpha_k(i,j)},\quad i\ne j, \quad\text{and}\quad B_{i,i}=\sum_{k=1}^{a_{i,i}}(T_{n}^{\alpha_k(i,i)}+ T_{n}^{-\alpha_k(i,i)}).
\end{equation}
\tag{6}
$$
Here $B_{i,j}$ is an $n\times n$ matrix whose $(s,s')$th entry is equal to the number of edges between the vertices $v_{i,s}$ and $v_{j,s'}$. Recall that the Laplacian of the graph $H_{n}$ has the form where $D(H_{n})$ is a diagonal matrix whose entries are equal to the degrees of the vertices of $H_{n}$. We denote by $d(v_i)$ the outdegree of the vertex $v_i$ in the graph $H$ (the number of tail ends adjacent to this vertex).To make the description of the block structure of the Laplacian more convenient, consider the following auxiliary polynomials:
$$
\begin{equation*}
p_{i,i}(z)=d(v_i)-\sum_{k=1}^{a_{i,i}}(z^{\alpha_{k}(i,i)} +z^{-\alpha_{k}(i,i)})\quad\text{and}\quad p_{i,j}(z)=-\sum_{k=1}^{a_{i,j}}z^{\alpha_k(i,j)},\ \ i\ne j.
\end{equation*}
\notag
$$
Note that the $(i,j)$th block of the block matrix $L(H_{n})=(L_{i,j})_{i,j=1,2,\dots,r}$ can be represented in the form $L_{i,j}=p_{i,j}(T_n)$, where $T_n=\operatorname{circ}(0,1,0,\dots,0)$ is a circulant $n\times n$ matrix. Also consider the polynomial
$$
\begin{equation}
P(z)=\det\begin{pmatrix} p_{1,1}(z) & p_{1,2}(z) & \dots & p_{1,r}(z) \\ p_{2,1}(z) & p_{2,2}(z) & \dots & p_{2,r}(z) \\ \vdots & \vdots & \ddots & \vdots \\ p_{r,1}(z) & p_{r,2}(z) & \dots & p_{r,r}(z)\\ \end{pmatrix}.
\end{equation}
\tag{7}
$$
In what follows we call $P(z)$ the voltage polynomial of the cyclic covering $H_n$. Remark 8.1. For a circulant graph $C_n(s_1,s_2,\dots,s_k)$ the voltage polynomial coincides with the associated Laurent polynomial Notice the following important properties of the voltage polynomial $P(z)$ (see [50], Lemma 5.2). Lemma 8.1. The following relations hold: $P(z)=P(1/z)$, $P(1)=0$, $P'(1)=0$, and $P''(1)< 0^{}$. In particular, $P(z)$ has a zero of multiplicity $2$ at $z=1$. It will be convenient to formulate the main results of this section in terms of one more auxiliary polynomial. Since the voltage polynomial obeys the relation $P(z)=P(1/z)$, it can be written in the form
$$
\begin{equation*}
P(z)=a_0\biggl(z^s+\frac{1}{z^s}\biggr)+a_{1}\biggl(z^{s-1}+ \frac{1}{z^{s-1}}\biggr)+\cdots+a_{s-1}\biggl(z+\frac{1}{z}\biggr)+a_s.
\end{equation*}
\notag
$$
Using the relation $\dfrac{1}{2}\biggl(z^n+\dfrac{1}{z^n}\biggr)= T_n\biggl(\dfrac{1}{2}\biggl(z+\dfrac{1}{z}\biggr)\biggr)$ we obtain
$$
\begin{equation*}
P(z)=Q\biggl(\frac{1}{2}\biggl(z+\frac{1}{z}\biggr)\biggr),
\end{equation*}
\notag
$$
where
$$
\begin{equation*}
Q(w)=2a_0T_s(w)+2a_1T_{s-1}(w)+\cdots+2a_{s-1}T_{1}(w)+a_s.
\end{equation*}
\notag
$$
We call $Q(w)$ the Chebyshev transform of the polynomial $P(z)$. Note that $Q(w)$ is a polynomial of degree $s$ with leading coefficient $\widetilde{a}_0=2^sa_0$. Note also the following useful relation: 8.1. Theorem on the number of spanning trees in a cyclic coveringTheorem 6.2 in [50] can be reformulated in the following way. Theorem 8.1. Consider a cyclic covering $H_n$, and let $P(z)$ be its voltage polynomial and $Q(w)$ be the Chebyshev transform of the polynomial $P(z)$. Then the number $\tau(n)$ of spanning trees in $H_{n}$ can be calculated by the formula where the product is taken over all the zeros of $Q(w)$ different from 1, and $\eta$ is the absolute value of the leading coefficient of $P(z)$. Remark 8.2. Comparing this result with Theorem 7.1 we can note that in the case of circulant foliations 8.2. The asymptotic behaviour of the number of spanning trees in a cyclic coveringIn this subsection we present a formula that describes the asymptotic behaviour of $\tau(H_n)$ as $n\to\infty$. The main result is given by the following theorem, established in [50] (see Theorem 8.1 there). Theorem 8.2. The asymptotic behaviour of the number of spanning trees in a cyclic covering $H_n$ is described by the formula where $A=\exp\biggl(\displaystyle\int_{0}^{1}\log |P(e^{2 \pi \mathtt{i} t})|\,dt\biggr)$ is the Mahler measure of the voltage polynomial $P(z)$. 9. Rooted spanning forests in circular graphs9.1. Counting rooted spanning forests in circulant graphsFirst of all, consider the case of circulant graphs with vertices of even degree. In this case the following two theorems proved in [33] are valid. In their statements the graph is not assumed to be connected. Theorem 9.1. The number $f_{G}(n)$ of rooted spanning forests in a circulant graph $G=C_{n}(s_1,s_2,\dots,s_k)$, $1\leqslant s_1< s_2<\cdots< s_k< n/2$, is given by the formula where the $w_{p},\,p=1,2,\dots,s_{k}$, are all the zeros of the algebraic equation and $T_{s}(w)$ is the Chebyshev polynomial of the first kind of degree $s$. Let us give a sketch of the proof. The set of eigenvalues of the matrix $I_n+L(G)$ has the form
$$
\begin{equation*}
\mu_{j}=P(\varepsilon_{n}^{j})=2k+1- \sum_{i=1}^k(\varepsilon_{n}^{j s_i}+\varepsilon_{n}^{-j s_{i}}),\qquad j=0,\dots,n-1.
\end{equation*}
\notag
$$
The number of rooted spanning forests can be represented by the formula
$$
\begin{equation*}
f_{G}(n)=\det(I_n+L(G))=\prod_{j=0}^{n-1}P(\varepsilon_{n}^{j}).
\end{equation*}
\notag
$$
Since $P(z)=P(1/z)$, all the zeros of $P(z)$ come in pairs:
$$
\begin{equation*}
z_{1},\frac{1}{z_{1}}\,,\quad z_{2},\frac{1}{z_{2}}\,,\quad \dots,\quad z_{s_{k}},\frac{1}{z_{s_{k}}}\,.
\end{equation*}
\notag
$$
Further, taking into account that $f_{G}(n)$ is positive, with regard to the main properties of resultants ([75], Chap. 3) we obtain
$$
\begin{equation*}
\begin{aligned} \, \prod_{j=0}^{n-1}P(\varepsilon_{n}^{j})&= \operatorname{Res}(P(z),z^n-1)=|\operatorname{Res}(z^n-1,P(z))| \\ &=\biggl|\,\prod_{p=1}^{s_{k}}(z_{p}^{n}-1)(z_{p}^{-n}-1)\biggr|= \biggl|\,\prod_{p=1}^{s_{k}}(2T_{n}(w_{p})-2)\biggr|. \end{aligned}
\end{equation*}
\notag
$$
The last equality is due to the following property of Chebyshev polynomials:
$$
\begin{equation*}
T_{n}\biggl(\frac{1}{2}(z+z^{-1})\biggr)=\frac{1}{2}(z^{n}+z^{-n}).
\end{equation*}
\notag
$$
Moreover, we put $w_{p}=(z_{p}+1/z_{p})/2$, $p=1,\dots,s_{k}$. These numbers are the roots of the equation $\sum_{j=1}^{k}(2T_{j}(w)-2)=1$. The following theorem allows one to count the rooted forests in a circulant graph with vertices of odd degree. Its proof is based on the same arguments as the proof of Theorem 9.1. The graph is still not assumed to be connected. Theorem 9.2. Let $C_{2n}(s_{1},s_{2},\dots,s_{k},n)$, $1\leqslant s_{1}<s_{2}<\cdots<s_{k}<n$, be a circulant graph with vertices of odd degree. Then the number $f_{G}(n)$ of rooted spanning forests in the graph $G=C_{2n}(s_1,s_2,\dots,s_k,n)$ is given by the formula where the $u_p$ and $v_p$, $p=1,2,\dots,s_k$, are the roots of the algebraic equations respectively. Here and $T_s(w)$ is a Chebyshev polynomial of the first kind. 9.2. Arithmetic properties of the number of rooted spanning forestsIn the case of circulant graphs with vertices of odd degree the following result holds ([33], Theorem 7.1). Theorem 9.3. Let $f_{G}(n)$ denote the number of rooted spanning forests in the circulant graph Let $p$ be the number of odd elements in the sequence $s_1,s_2,\dots,s_k$ and $q$ be the square-free part of $p$. Then there exists an integer sequence $a(n)$ such that (a) $f_{G}(n)=a(n)^2$ if $n$ is odd; (b) $f_{G}(n)=q\,a(n)^2$ if $n$ is even. Proof. This is based on the following arguments. Since each eigenvalue of the matrix $I_n+L(G)$ (maybe with the exception of the term in the middle of the sequence $\mu_{j}$) comes twice. Hence $f_{G}(n)=\prod_{j=0}^{n-1}\mu_j$ equals $\bigl(\prod_{j=0}^{(n-1)/2}\mu_j\bigr)^2$ if $n$ is odd and $\mu_{n/2}\bigl(\prod_{j=0}^{n/2-1}\mu_j\bigr)^2$ if $n$ is even. Note that all numbers $\mu_{j}$ are algebraic integers, since they are zeros of a polynomial with integer coefficients. The product of an algebraic integer and all of its Galois conjugates is always an integer; it is called the norm of this number. Each $\mu_{j}$ enters the products $\prod_{j=0}^{(n-1)/2}\mu_j$ and $\prod_{j=0}^{n/2-1}\mu_j$ with all of its Galois conjugate elements. Therefore, both products are integers. To complete the proof note that the eigenvalue $\mu_{n/2}$ in the middle of the series (if it exists) equals
$$
\begin{equation*}
P(-1)=2k+1-\sum_{p=1}^{k}((-1)^{s_p}+(-1)^{-s_p})=4p+1,
\end{equation*}
\notag
$$
where $p$ is the number of odd members of the sequence $s_1,s_2,\dots,s_k$. The following theorem describes the arithmetic properties of the number of rooted spanning forests in circulant graphs with vertices of odd degree ([33], Theorem 5.2). Theorem 9.4. Let $f_{G}(n)$ be the number of rooted spanning forests in the circulant graph and $p$ be the number of odd elements in the sequence $s_1,s_2,\dots,s_k$. Denote by $q$ and $r$ the square-free parts of the integers $4p+1$ and $4p+3$, respectively. Then there exists an integer sequence $a(n)$ such that (a) $f_{G}(n)=q\,a(n)^2$ if $n$ is even; (b) $f_{G}(n)=r\,a(n)^2$ if $n$ is odd. 9.3. The asymptotic behaviour of the number of rooted spanning forestsIn a circulant graph with vertices of even degree we have the following results, obtained in [33]. Theorem 9.5. The asymptotic behaviour of the number of rooted spanning forests in the circulant graph is given by the formula where $A=\exp\biggl(\displaystyle\int_0^1 \log(P(e^{2\pi\mathtt{i}t}))\,dt\biggr)$ is the Mahler measure of the associated Laurent polynomial $P(z)=2k+1-\sum_{i=1}^k(z^{s_i}+z^{-{s_i}})$. Proof. This is based on the following arguments. By Theorem 9.1 the number $f_{G}(n)$ of spanning forests is given by $f_{G}(n)=\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|$, where $w_{s}=(z_{s}+z_{s}^{-1})/2$. We have $T_{n}(w_s)=(z_{s}^{n}+z_{s}^{-n})/2$, where the $z_{s}$ and $1/z_{s}$, $s=1,\dots,s_{k}$, are all the zeros of the polynomial $P(z)$. If $\varphi\in\mathbb{R}$, then
$$
\begin{equation*}
P(e^{\mathtt{i}\varphi})=2k+1-\sum_{j=1}^{k} (e^{s_{j} \mathtt{i}\varphi}+e^{-s_{j}\mathtt{i}\varphi})= 2k+1-2\sum_{j=1}^{k}\cos(s_{j}\varphi)\geqslant1.
\end{equation*}
\notag
$$
Hence $P(z)$ has no zeros equal to 1 in absolute value, and $|z_{s}|\ne1$ for all $s$. Switching $z_s$ with $1/z_s$ if necessary we can assume that $|z_s|>1$ for all $s$. Then $T_n(w_s)\sim z_s^n/2$ as $n\to \infty$. Therefore, $|2T_n(w_s)-2|\sim|z_s|^n$ as $n\to\infty$. This yields the relation
$$
\begin{equation*}
\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|\sim \prod_{s=1}^{s_k}|z_s|^n= \prod_{P(z)=0,\,|z|>1}|z|^n=A^n,
\end{equation*}
\notag
$$
where $A=\prod_{P(z)=0,\,|z|>1}|z|$ is the Mahler measure of the polynomial $P(z)$. In view of the results presented in § 2.6 it can be found by the formula
Finally, we have The asymptotic behaviour of the number of rooted spanning forests in a circulant graph with vertices of odd degree is described by the following theorem. Theorem 9.6. The number $f_{G}(n)$ of rooted forests in the circulant graph exhibits the following asymptotic behaviour: where $K=\exp\biggl(\displaystyle\int_0^1\log |P(e^{2\pi\mathtt{i}t})^{2}-1|\,dt\biggr)$ is the Mahler measure of the Laurent polynomial $P(z)^2-1$ and $P(z)=2k+2-\sum_{i=1}^k(z^{s_i}+z^{-s_i})$. 9.4. ExamplesWe give a series of examples illustrating the results presented in this section. Example 9.1 (the cyclic graph $C_n=C_n(1)$). By Theorem 9.1, to find the number of rooted spanning forests, in this case we need to find all roots of the equation $1+2-2T_{1}(w)=0$. This root $w$ equals $3/2$. Hence $f_{G}(n)=2T_{n}(3/2)-2$. Further, by Theorem 9.5 we have Example 9.2 (the circulant graph $C_{n}(1,2)$). Following Theorem 9.1 for the circulant graph with two jumps $1$ and $2$, we find it necessary to solve the equation $1+4-2T_{1}(w)-2T_{2}(w)=0$. Its roots are Hence where $A=(7+\sqrt{5}+\sqrt{38+14\sqrt{5}}\,)/4\simeq 4.3902568\dots$ . By Theorem 9.3 there exists a sequence of integers $a(n)$ such that $f_{G}(n)=5a(n)^2$ if $n$ is even and $f_{G}(n)=a(n)^2$ if $n$ is odd. Example 9.3 (the circulant graph $C_{n}(1,3)$). Let $w_{1}$, $w_{2}$, and $w_{3}$ be the roots of the cubic equation $1+4-2T_{1}(w)-2T_{3}(w)=0$. Then Example 9.4 (the Möbius ladder $C_{2n}(1,n)$). By Theorem 9.2 it is necessary to solve two algebraic equations: $3-2T_{1}(w)=0$ and $5-2T_{1}(w)=0$. The corresponding roots are: $u_{1}=3/2$ and $v_{1}=5/2$. Hence 10. Circulant foliations of graphsLet $H_n=H(G_{1},\,G_{1},\dots,\,G_{m})$ be the circulant foliation considered in § 7. To present the results of this section we introduce the following auxiliary polynomials. Let
$$
\begin{equation*}
P_{f}(z)=\det(I+L(H,X))\quad\text{and}\quad Q_{f}(w)=\det(I+L(H,W)),
\end{equation*}
\notag
$$
where the generalized Laplacians $L(H,X)$ and $L(H,W)$ are the same as in § 7. As above, these polynomials are related by the equality $P_{f}(z)=Q_{f}((z+1/z)/2)$. Denote by $\zeta$ the absolute value of the leading coefficient of $P_{f}(z)$. 10.1. The number of rooted spanning forests in a circulant foliationThe following result was established in [31], Theorem 3.3. Theorem 10.1. The number $f(n)$ of rooted spanning forests in the circulant foliation $H_{n}(G_1,G_2,\dots,G_m)$ is given by the formula where $s=s_{1,k_1}+s_{2,k_2}+\cdots+s_{m,k_m}$, the $w_p$, $p=1,2,\dots,s$, are all the roots of the equation $Q_{f}(w)=0$, and $\zeta$ is the absolute value of the leading coefficient of the polynomial $P_{f}(z)$. 10.2. Arithmetic properties of the number of rooted spanning forests in a circulant foliationThe following result was obtained in [31], Theorem 4.1. Theorem 10.2. Let $f(n)$ be the number of rooted spanning forests in the circulant foliation $H_n$ and $f(H)$ be the number of rooted spanning forests in the base graph $H$. Denote the square-free part of the integer $Q_{f}(-1)$ by $p$. Then there exists an integer sequence $a(n)$ such that (a) $f(n)=f(H)\,a(n)^{2}$ if $n$ is odd; (b) $f(n)=p\,f(H)\,a(n)^{2}$ if $n$ is even. 10.3. The asymptotic behaviour of the number of rooted spanning forests in a circulant foliationThe following results was proved in [31], Theorem 5.1. Theorem 10.3. The number $f(n)$ of rooted spanning forests in the circulant foliation $H_n$ exhibits the following asymptotic behaviour: where is the Mahler measure of the polynomial $P_{f}(z)$. 10.4. Examples Example 10.1 (the $I$-graph $I(n,k,l)$ and the generalized Petersen graph $\operatorname{GP}(n,k)$). Let $H$ be a path graph with two vertices, and put $G_{1}=C_{n}(k)$ and $G_{2}=C_{n}(l)$. Consider the graphs Example 10.2 (a generalized $Y$-graph). Consider a generalized $Y$-graph Then where $A_{i}(w)=2k_{i}+2-\sum_{j=1}^{k_{i}}2T_{s_{i,j}}(w)$. In the particular case where $G_{1}=G_{2}=G_{3}=C_{n}(1)$ we have and $\zeta=4$. Here
$$
\begin{equation*}
f(n)=4^n\biggl(2T_{n}\biggl(\frac{13}{8}\biggr)-2\biggr)(2T_{n}(2)-2)^2.
\end{equation*}
\notag
$$
By Theorem 10.2 there exists an integer sequence $a(n)$ such that $f(n)=f(1)a(n)^2$ if $n$ is odd, and $f(n)=21f(1)a(n)^2$ if $n$ is even; in addition, $f(1)=20$. Theorem 10.3 suggests the following asymptotic: Example 10.3 (a generalized $H$-graph). Consider a generalized $H$-graph of the form $H_{n}(G_{1},G_{2},G_{3},G_{4})$, where $G_{i}$, $i=1,2,3,4$, are some fixed circulant graphs $C_{n}(s_{ i,1},\,s_{i,2},\dots,s_{i,k_i})$. For this graph we have 11. The Jacobian groups of circulant graphsThe Jacobian group, which is also referred to as the sandpile group, the Picard group, the critical group, the dollar group, or the group of components, was independently introduced by many authors. An important specific feature of the Jacobian of a grapf is that it has a non-spectral nature. There exist graphs with the same spectrum but different Jacobians. At the same time there exist graphs with the same Jacobian, but different spectra. In this survey we present structural formulae for the computation of the Jacobians of circulant graphs and their simplest analogues. The basic technique for the computation of all invariants mentioned above deals with Chebyshev polynomials and their properties. The notion of the Jacobian group of a graph, which is also referred to as the Picard group, the critical group, the dollar group, or the sandpile group, was independently introduced by many authors [22], [6], [9], [4]. This concept is also a discrete version of the notion of 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 in the graph. The aim of this section is to describe the structure of the Jacobian group for circulant graphs. For simplest circulant graphs the Jacobian group will be described explicitly, whereas in the general case we will propose a convenient method for its computation. 11.1. Graphs with vertices of even degreeWe introduce the following definition. Let $P(z)$ be the Laurent polynomial of the form where $a_1,a_2,\dots,a_{s-1}$, $p$, $s$ are integers and $s$ is positive. The companion matrix $\mathcal{A}$ of the polynomial $P(z)$ is defined by
$$
\begin{equation*}
\mathcal{A}=\biggl(\begin{array}{c}\begin{array}{c|c} {0} & I_{s-1}\end{array}\\\hline -1,-a_1,\dots,-a_{s-1}\\ \end{array}\biggr),
\end{equation*}
\notag
$$
where $I_{s-1}$ is the identity $(s-1)\times(s-1)$-matrix. Since $\det(\mathcal{A})=(-1)^{s}$, the matrix $\mathcal{A}$ is invertible and the inverse matrix $\mathcal{A}^{-1}$ is an integer matrix too. The companion matrix of the polynomial $-P(z)$ is also set to be $\mathcal{A}$. The structure of the Jacobian group for the circulant graph with vertices of even degree is described by the following theorem ([60], Theorem 2.1). Theorem 11.1. Let $G=C_{n}(s_{1},s_{2},\dots,s_{k})$ be the circulant graph with jumps satisfying $1\leqslant s_{1}<s_{2}<\cdots<s_{k}< n/2$. Then the Jacobian group $\operatorname{Jac}(G)$ is isomorphic to the torsion group of the cokernel of the operator $\mathcal{A}^n-I$, where $\mathcal{A}$ is the companion matrix of the polynomial $2k-\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}})$. As an application of Theorem 11.1, consider the following result, which was independently obtained in [38] and [60]. Example 11.1 (the graph $C_n(1,2)$). The Jacobian group $\operatorname{Jac}(C_n(1,2))$ is isomorphic to $\mathbb{Z}_{(n,F_n)}\oplus\mathbb{Z}_{F_n}\oplus\mathbb{Z}_{\{n,F_n\}}$, where $(a,b)=\operatorname{gcd}(a,b)$ and $\{a,b\}=\operatorname{lcm}(a,b)$ are the greatest common divisor and the least common multiple, respectively, of the integers $a$ and $b$, and $F_n$ is the $n$th Fibonacci number. In the following example we present Theorem 2.2 from [60]. Example 11.2 (the graph $C_n(1,3)$). Consider the two periodic sequences $\mu(n)$ and $\eta(n)$ defined by Set
$$
\begin{equation*}
\begin{gathered} \, \Delta_1=\operatorname{gcd}(n,s,t,u,v),\quad \Delta_2=\operatorname{gcd}(s,t,nu,nv), \\ \Delta_3=\operatorname{gcd}(ns,nt,su+tv,sv-tu),\quad \Delta_4=\operatorname{gcd}(s^2+t^2,n(su+tv),n(sv-tu)), \\ \text{and} \qquad \Delta_5=\frac{n}{10}(s^2+t^2). \end{gathered}
\end{equation*}
\notag
$$
Then the Jacobian group $\operatorname{Jac}(C_n(1,3))$ is isomorphic to $\mathbb{Z}_{d_1}\oplus\mathbb{Z}_{d_2}\oplus\mathbb{Z}_{d_3}\oplus \mathbb{Z}_{d_4}\oplus \mathbb{Z}_{d_5}$, where Moreover, the number of spanning trees in the graph $C_n(1,3)$ is given by the formula11.2. Graphs with vertices of odd degreeThe following theorem (in an equivalent form) was stated in [60]. The technique employed in its proof was presented in the later work [32]. Theorem 11.2. Let be a circulant graph with vertices of odd degree. The its Jacobian group $\operatorname{Jac}(G)$ is isomorphic to the torsion group of the cokernel of the operator where $\mathcal{A}$ is the companion matrix of the polynomial $\bigl(2k+1-\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})\bigr)^2-1$. For example we present the following result obtained in [17], [69] and [60] by different methods. Example 11.3 (the Möbius ladder $M(n)=C_{2n}(1,n)$). Let and where $T_m=T_m(2)$ and $U_{m-1}=U_{m-1}(2) $ are Chebyshev polynomials of the first and second kind, respectively. Then the Jacobian matrix $\operatorname{Jac}(M(n))$ of the Möbius ladder $M(n)$ is isomorphic to the group $\mathbb{Z}_{(n,H_m)}\oplus\mathbb{Z}_{H_m}\oplus\mathbb{Z}_{3\{n,H_m\}}$ if $n=2m+1$ is odd, to $\mathbb{Z}_{(n,T_m)}\oplus\mathbb{Z}_{T_m}\oplus\mathbb{Z}_{2\{n,T_m\}}$ if $n=2m$ and $m$ is even, and to $\mathbb{Z}_{(n,T_m)/2}\oplus \mathbb{Z}_{2T_m}\oplus\mathbb{Z}_{2\{n,T_m\}}$ if $n=2m$ and $m$ is odd. 11.3. Graphs with unfixed jumpsThe aim of this subsection is to describe the critical group of the circulant graph of the form $G=C_{\beta n}(s_1,s_2,\dots,s_k,\alpha_1n,\alpha_2n, \dots,\alpha_\ell n)$, which has $\beta n$ vertices and $k+\ell$ jumps, the first $k$ of which have the same value, while the remaining $\ell$ of which depend linearly on $n$. The particular case $\beta=1$, $\ell=0$ (a circulant graph with constant jumps) was considered before. Consider an integer $m\times n$ matrix $M$ as a linear mapping from $\mathbb{Z}^{m}$ to $\mathbb{Z}^{n}$. Then $M$ has the image $\operatorname{im}M=M^{t}\mathbb{Z}^{m}$ and the cokernel $\operatorname{coker}M=\mathbb{Z}^{n}/\operatorname{im}M$. Recall that the Jacobian $\operatorname{Jac}(G)$ of the graph $G$ is isomorphic to the torsion group of the cokernel of its Laplacian matrix $L(G)$. The main result of this subsection is presented in the following theorem, established in [63]. Theorem 11.3. Let $G=C_{\beta n}(s_1,s_2,\dots,s_k,\alpha_1n, \alpha_2n,\dots,\alpha_\ell n)$ be a connected circulant graph, where $1\leqslant s_1<s_2<\cdots<s_k<[\beta n/2]$ and $1\leqslant \alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant [\beta/2]$ are integers. Let Denote by $\mathcal{A}$ the companion matrix of the Laurent polynomial Then the Jacobian group $\operatorname{Jac}(G)$ is isomorphic to the torsion group of the cokernel of the integer $2\beta s_k\times 4\beta s_k$ matrix $(P(\mathcal{A})+l(\mathcal{A}^n),\mathcal{A}^{\beta\,n}-I_{2\beta s_k})$. Moreover, the rank of the Abelian group $\operatorname{Jac}(G)$ is always at least $2$ and does not exceed $2\beta s_k-1$. Both estimates are sharp. Sketch of the proof. First of all, note that $R_\beta(z)$ is the resultant of the Laurent polynomials $P(z)+l(x)$ and $x^\beta-1$ in the variable $x$. Therefore, $R_\beta(z)$ is a monic polynomial with integer coefficients. Following the proof of the polynomial remainder theorem for resultants (Theorem 3.2 in [75]), we find Laurent polynomials $p(x,z)$ and $q(x,z)$ in $x$ and $z$ with integer coefficients such that Note that the Laplacian $L(G)$ of the graph $G$ is specified by the matrix $-P(T_{\beta n})-l(T_{\beta n}^n)$, where $T_{\beta n}=\operatorname{circ}(0,1,0,\dots,0)$ is the circulant $\beta\, n \times \beta\, n$ shift matrix. Let $\mathbb{A}$ be the Abelian group generated freely by the infinite set of elements $x_i$, $i\in\mathbb{Z}$. Consider the group endomorphism $T$ of $\mathbb{A}$ acting by the rule $T\colon x_i\to x_{i+1}$. Then using the notation in [49], we represent the cokernel $L(G)$ as the Abelian group with the following presentation:
$$
\begin{equation*}
\begin{aligned} \, \operatorname{coker}(L(G))&=\langle x_i,\,i\in\mathbb{Z}\colon (P(T)+l(T^n))x_j=0,(T^{\beta\,n}-1)x_j=0,\,j\in\mathbb{Z}\rangle \\ &=\langle x_i,\,i\in\mathbb{Z}\colon (P(T)+l(T^n))x_j=0,(T^{\beta\,n}-1)x_j=0, \\ &\qquad p(T^n,T)(P(T)+l(T^n))x_j+q(T^n,T)(T^{\beta\,n}-1)x_j=0,\, j\in\mathbb{Z}\rangle \\ &=\langle x_i,\,i\in\mathbb{Z}\colon (P(T)+l(T^n))x_j=0,(T^{\beta\,n}-1)x_j=0,R_{\beta}(T)x_j=0\rangle. \end{aligned}
\end{equation*}
\notag
$$
Put $A=P(T)+l(T^n)$, $B=T^{\beta\,n}-1$, and $C=R_{\beta}(T)$. Since the leading coefficient of the polynomial $R_{\beta}(z)$ is equal to one, the $\mathbb{Z}$-module $\operatorname{coker} C=\mathbb{A}/\operatorname{im}C$ is freely generated by the elements $u_1,u_2,\dots,u_s$, where $s=2\beta s_k$ is the degree of $R_{\beta}(z)$ and $u_i=[x_i]$ is the image of $x_i$ under the canonical map $\mathbb{A}\to\mathbb{A}/\operatorname{im}C$. In the basis $u_1,u_2,\dots,u_s$ the action of the operator $T\big|_{\operatorname{coker}C}$ is determined by the companion matrix $\mathcal{A}$ of the polynomial $R_\beta(z)$. Hence the actions of the endomorphisms $A\big|_{\operatorname{coker}C}$ and $B\big|_{\operatorname{coker}C}$ on $\operatorname{coker}C$ are given by the $s\times s$ matrices $P(\mathcal{A})+l(\mathcal{A}^n)$ and $\mathcal{A}^{\beta\,n}-I_{2\beta s_k}$, respectively. An application of Lemma 1 from [49] completes the proof of the theorem. The simplest circulant graph with non-fixed jumps is the Möbius ladder with double rungs $C''_{2n}(1,n)$. Let us illustrate the above theorem with the following example. Example 11.4 (the graph $C''_{2n}(1,n)$ — Möbius ladder with double rungs). The Jacobian group of the Möbius ladder with double rungs is isomorphic to $\mathbb{Z}_{(n,a(n))}\oplus\mathbb{Z}_{a(n)}\oplus \mathbb{Z}_{4\{n,a(n)\}/(2,n)}$, where $(l,m)=\operatorname{gcd}(l,m)$, $\{l,m\}=\operatorname{lcm}(l,m)$, and $a(n)$ is the sequence $A079496$ in the On-Line Encyclopedia of Integer Sequences (OEIS). Moreover, $a(n)=T_m(3)$ if $n=2m$, and $a(n)=2U_{m-1}(3)+T_m(3)$ if $n=2m+1$, where $T_m(x)$ and $U_{m-1}(x) $ are Chebyshev polynomials of the first and second kind, respectively. 11.4. Jacobian groups of cones over graphsThe joint of graphs $G$ and $H$ is the graph $G*H$ obtained from the disjoint union of $G$ and $H$ by adding edges joining each vertex of $G$ with each vertex of $H$. If $H=K_{1}$ is the one-vertex graph, then the joint $\widehat{G}=G*K_{1}$ is called the cone over the graph $G$. Let us present an interesting result from graph theory, which was independently obtained several times by many authors (see, for example, [15] and the references there). Theorem 11.4. The number of spanning trees in the cone $\widehat{G}$ over a graph $G$ coincides with the number of rooted spanning forests in $G$. Note that there exists a natural one-to-one correspondence between the spanning trees in the cone $\widehat{G}$ and the rooted spanning forests in the graph $G$. Indeed, consider $\widehat{G}$ as the joint of $G$ with the one-vertex graph $\{v_0\}$. Then each spanning tree $t$ in $\widehat{G}$ contains the vertex $v_0$. Let the $v_0v_j$, $j=1,2,\dots,k$, be all the edges of the graph $t$ coming out of $v_0$. Then $f=t\cap G$ is a spanning forest in the graph $G$ consisting of $k$ trees $t_1,t_2,\dots,t_k$ chosen so that $v_j$ is a vertex of the tree $t_j$. So the pairs $(t_j,v_j)$, $j=1,2,\dots,k$, form a rooted spanning forest in $G$. Conversely, if $(t_j,v_j)$, $j=1,2,\dots,k$, is a rooted spanning forest in $G$, then the graph $t$ obtained as the union of the vertex $v_0$, the edges $v_0v_j$, and the trees $t_j$, $j=1,2,\dots,k$, is a spanning tree in $\widehat{G}$. The following theorem was independently proved by different authors (see, for example, [28], Remark 3, and [32], Theorem 2). Theorem 11.5. Consider a graph $G$ on $n$ vertices. Then the Jacobian group of a cone over the graph $G$ is isomorphic to the torsion group of the cokernel of the linear operator $I_n+L(G)$, where $L(G)$ is the Laplacian matrix of the graph $G$ and $I_n$ is the identity $n\times n$ matrix. Note that $\operatorname{coker}(I_{n}+L(G))$ is a finite Abelian group of order $\det(I_{n}+L(G))$. According to (1), this number coincides with the number of rooted spanning forests in $G$. Following [32] we call $\operatorname{coker}(I_{n}+L(G))$ the forest group of the graph $G$ and denote it by $F(G)$. Then the statement of Theorem 11.5 can be rephrased as follows: The Jacobian group $\operatorname{Jac}(\widehat{G})$ of the cone $\widehat{G}$ over a graph $G$ is isomorphic to the forest group $F(G)$. 11.5. The forest group of a circulant graphFor a circulant graph with vertices of even degree the following theorem holds ([32], Theorem 3). Theorem 11.6. Consider a cone $\widehat{G}$ over the circulant graph Then the Jacobian group $\operatorname{Jac}({\widehat{G}})$ is isomorphic to the group $\operatorname{coker}(\mathcal{A}^n-I)$, where $\mathcal{A}$ is the companion matrix of the Laurent polynomial $2k+1-\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}})$. Consider a $(2k+1)$-valent circulant graph
$$
\begin{equation*}
G=C_{2n}(s_{1},s_{2},\dots,s_{k},n),\qquad 1\leqslant s_{1}<s_{2}<\cdots<s_{k}<n.
\end{equation*}
\notag
$$
In this case we have the following result established in [32], Theorem 4. Theorem 11.7. Let $\widehat{G}$ be a cone over the circulant graph $G$. Then the group $\operatorname{Jac}({\widehat{G}})$ is isomorphic to $\operatorname{coker}\bigl(\mathcal{A}^n-(2k+2)I+\sum_{j=1}^{k} (\mathcal{A}^{s_{j}}+\mathcal{A}^{-s_{j}})\bigr)$, where $\mathcal{A}$ is the companion matrix of the Laurent polynomial $\bigl(2k+2-\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})\bigr)^2-1$. To illustrate the use of the above theorem consider the following example. Example 11.5 (the forest group of the Möbius ladder). Let $\widehat{G}$ be a cone over the Möbius ladder $G=C_{2n}(1,n)$. Let $n=2m+1$ be an odd integer, and define the Chebyshev polynomial of the fourth kind by 12. Plans’s periodicity theorem for reduced JacobiansPlans’s theorem [74] states that for odd $n$ the first homology group of the $n$-fold cyclic covering of the three-dimensional sphere branched over a knot is the direct product of two copies of an Abelian group. A similar statement holds for even $n$, in which case one has to take the quotient of the homology group of the $n$-fold covering by the reduced homology group of the twofold covering. (A modern proof of this theorem can be found in [29] and [84].) The aim of this section is to establish similar results for the Jacobian groups (critical groups) of circulant graphs. Moreover, it will also be shown that the Jacobian group of a circulant graph on $n$ vertices reduced modulo a fixed finite Abelian group is a periodic function of $n$. In [66] we noticed some parallels between results describing the homology groups of branched cyclic coverings over knots and results in the theory of cyclic coverings over graphs. Let us present a glossary that establishes a natural correspondence between objects of knot theory and their analogues in graph theory: $\bullet$ a knot $K$ in the sphere $\mathbb{S}^3$ corresponds to a vertex $v$ of the cone $\widehat{G}=\{v\}\star G$; $\bullet$ the Alexander polynomial of $K$ corresponds to the associated Laurent polynomial of the graph $G$; $\bullet$ the complement $\mathbb{S}^3\setminus K$ corresponds to the graph $G$; $\bullet$ a cyclic covering over $\mathbb{S}^3\setminus K$ corresponds to a cyclic covering over the graph $G$; $\bullet$ the cyclic covering $M_n$ of the sphere $\mathbb{S}^3$ branched over $K$ corresponds to the cyclic covering $\widehat{G}_n$ of the cone $\widehat{G}=\{v\}\star G$ branched over $v$; $\bullet$ the homology group $H_1(M_n,\mathbb{Z})$ corresponds to the Jacobian group $\operatorname{Jac}(\widehat{G}_n)$. 12.1. Plans’s theorem for circulant graphsThe simplest formulation of Plans’s theorem for graphs is obtained in the case where $G$ is the one-vertex graph with $k$ loops [66]. In this case $G_n$ is the circulant graph of the form $C_{n}(s_{1},s_{2},\dots,s_{k})$ and $\widehat{G}_n$ is the cone over this graph. Theorem 12.1. Let $G_n=C_{n}(s_{1},s_{2},\dots,s_{k})$ be a circulant graph on $n$ vertices and $\widehat{G}_n$ be a cone over this graph. Then for any odd integer $n$ the group $\operatorname{Jac}(\widehat{G}_n)$ is the direct product of two copies of a finite Abelian group. If $n$ is even, then $\operatorname{Jac}(\widehat{G}_2)$ is naturally embedded in the group $\operatorname{Jac}(\widehat{G}_n)$, and the quotient group $\operatorname{Jac}(\widehat{G}_n)/\operatorname{Jac}(\widehat{G}_2)$ has the form of the direct product of two copies of a finite Abelian group. Sketch of the proof. First, let $n=2m+1$ be an odd integer. By Theorem 11.6 the Jacobian group $\operatorname{Jac}({\widehat{G}})$ is isomorphic to the group $\operatorname{coker}(\mathcal{A}^n-I)$, where $\mathcal{A}$ is the companion matrix of the Laurent polynomial $2k+1-\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}})$. In view of the elementary relation Lemma 12.1. There exists an integer unimodular matrix $U$ such that the product $U(\mathcal{A}+\mathcal{A}^{-1})U^{-1}$ is a block matrix of the form $\begin{pmatrix} G & 0 \\ 0 & J\,G\,J\end{pmatrix}$, where $G$ is an integer $s_{k}\times s_{k}$ matrix and $J$ is the antidiagonal matrix with antidiagonal of ones. Proof. Take $U$ to be the block matrix where $C=\biggl(\begin{array}{c}\begin{array}{c|c}0 & I_{s_k-1}\end{array} \\ \hline 0\,\dots\,0\end{array}\biggr)$ is the companion matrix of the polynomial $z^{s_k}$. It is easily verified that $\det(U)=1$.
The rest of the proof employs the fact that multiplication by an integer unimodular matrix does not change the cokernel of a linear operator. We have the following sequence of elementary equivalent matrices:
$$
\begin{equation*}
\begin{aligned} \, \mathcal{A}^{2m+1}-I&\sim p(\mathcal{A}+\mathcal{A}^{-1})\sim U\,p(\mathcal{A}+\mathcal{A}^{-1})\,U^{-1}\sim p(U\,(\mathcal{A}+\mathcal{A}^{-1})\,U^{-1}) \\ & \sim p\biggl(\begin{pmatrix} G & 0 \\ 0 & J\,G\,J \end{pmatrix}\biggr)\sim \begin{pmatrix} p(G) & 0 \\ 0 & p(J\,G\,J)\end{pmatrix}\sim \begin{pmatrix} p(G) & 0 \\ 0 & p(G)\end{pmatrix}. \end{aligned}
\end{equation*}
\notag
$$
This means that
$$
\begin{equation*}
\operatorname{coker}(\mathcal{A}^{2m+1}-I)=\operatorname{coker}(p(G)) \oplus\operatorname{coker}(p(G)).
\end{equation*}
\notag
$$
The proof in the case of odd $n$ is complete.
The proof of the theorem in the even case $n=2m$ is based on the identity and takes due account of the fact that the quotient group $\operatorname{Jac}(\widehat{G}_{2m})/\operatorname{Jac}(\widehat{G}_2)$ is isomorphic to the cokernel of the matrix $(\mathcal{A}^{2m}-1)(\mathcal{A}^2-1)^{-1}$.12.2. Reduced Jacobians and their periodicityIt is known that the homology groups of $n$-fold branched coverings over a knot with coefficients in a given cyclic group $\mathbb{Z}_m$ form a periodic sequence. Following [84] we write this assertion in a more general form. Let $M_n$ be a sequence of $n$-fold cyclic coverings branched over a fixed knot and $\mathbb{A}$ be a finite Abelian group. Then the sequence of homology groups $H_1(M_n,\mathbb{A})$ with coefficients in $\mathbb{A}$ is periodic. A similar theorem holds for unbranched coverings of the complement of the knot with respect to the homology sphere [76]. Recall that by the universal coefficient theorem
$$
\begin{equation*}
H_1(M_n,\mathbb{A})=H_1(M_n,\mathbb{Z})\otimes\mathbb{A}.
\end{equation*}
\notag
$$
To formulate a similar assertion for graphs we introduce the reduced Jacobian $\operatorname{Jac}_\mathbb{A}(G)$ of the graph $G$ by the Abelian group $\mathbb{A}$ as the group defined by the tensor product $\operatorname{Jac}(G)\otimes\mathbb{A}$. We represent a finite Abelian group $\mathbb{A}$ as a direct product $\mathbb{Z}_{q_1}\oplus\mathbb{Z}_{q_2}\oplus\cdots\oplus\mathbb{Z}_{q_k}$, where $q_1,q_2,\dots,q_k$ are appropriate prime powers, and put
$$
\begin{equation*}
\operatorname{Jac}_{q}(G)=\operatorname{Jac}(G)\otimes \mathbb{Z}_q.
\end{equation*}
\notag
$$
Then the reduced Jacobian $\operatorname{Jac}_\mathbb{A}(G)$ of the graph $G$ by the group $\mathbb{A}$ coincides with
$$
\begin{equation*}
\operatorname{Jac}_{q_1}(G)\oplus\operatorname{Jac}_{q_2}(G) \oplus\cdots\oplus\operatorname{Jac}_{q_k}(G).
\end{equation*}
\notag
$$
Note that reduced Jacobians play an important role in the discrete theory of dynamical systems [39], [72]. The following theorem holds ([66], Theorem 2). Theorem 12.2. Let $G_n=C_{n}(s_{1},s_{2},\dots,s_{k}),\,n=1,2,\dots$, be a sequence of circulant graphs and $\widehat{G}_n$ be the corresponding sequence of cones. Let $\mathbb{A}$ be an arbitrary finite Abelian group. Then the sequences of reduced (over $\mathbb{A}$) Jacobians $\operatorname{Jac}_\mathbb{A}(G_n)$ and $\operatorname{Jac}_\mathbb{A}(\widehat{G}_n)$ are periodic. To illustrate Theorem 12.2 we note that for the family of graphs $G_n=C_n(1,2)$ the periods of the reduced Jacobians $\operatorname{Jac}_{\,\mathbb{Z}_6}(G_{n})$ and $\operatorname{Jac}_{\,\mathbb{Z}_6}(\widehat{G}_{n})$ are equal to 12 and 5, respectively, and the corresponding periods for $\operatorname{Jac}_{\,\mathbb{Z}_7}(G_{n})$ and $\operatorname{Jac}_{\,\mathbb{Z}_7}(\widehat{G}_{n})$ are equal to 56 and 12, respectively.
Citation in format AMSBIB
\Bibitem{MedMed23} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|