Spanning trees in directed circulant graphs and cycle power graphs

Abstract

The number of spanning trees in a class of directed circulant graphs with generators depending linearly on the number of vertices $\beta n$, and in the nth and $(n-1)$th power graphs of the $\beta n$-cycle are evaluated as a product of $\lceil \beta /2\rceil -1$ terms.

1 Introduction

In this paper we study the number of spanning trees in a class of directed and undirected circulant graphs. Let $1\leqslant \gamma _1\leqslant \cdots \leqslant \gamma _d\leqslant \lfloor n/2\rfloor$ be positive integers. A circulant directed graph, or circulant digraph, on n vertices generated by $\gamma _1,\ldots ,\gamma _d$ is the directed graph on n vertices labelled $0,1,\ldots ,n-1$ such that for each vertex $v\in \mathbb {Z}/n\mathbb {Z}$ there is an oriented edge connecting v to $v+\gamma _m$ mod n for all $m\in \{1,\ldots ,d\}$. We will denote such graphs by $\overrightarrow{C}^{\gamma _1,\ldots ,\gamma _d}_n$. Similarly, a circulant graph on n vertices generated by $\gamma _1,\ldots \gamma _d$, denoted by $C^{\gamma _1,\ldots ,\gamma _d}_n$, is the undirected graph on n vertices labelled $0,1,\ldots ,n-1$ such that each vertex $v\in \mathbb {Z}/n\mathbb {Z}$ is connected to $v-\gamma _m$ mod n and to $v+\gamma _m$ mod n, for all $m\in \{1,\ldots ,d\}$. Circulant graphs and digraphs are used as models in network theory. In this context, they are called multi-loop networks, or double-loop networks when they are 2-generated, see for example [7, 8]. The number of spanning tree measures the reliability of a network.

The evaluation of the number of spanning trees in circulant graphs and digraphs has been widely studied, were both exact and asymptotic results have been obtained as the number of vertices grows, see [2, 6, 11–13] and references therein. In [3, 5], the authors showed that the number of spanning trees in such graphs satisfy linear recurrence relations. Yong, Zhang and Golin developed a technique in [13] to evaluate the number of spanning trees in a particular class of double-loop networks $\overrightarrow{C}^{p,\gamma n+p}_{\beta n}$. In the first section of this work, we derive a closed formula for these graphs, and more generally for d-generated circulant digraphs with generators depending linearly on the number of vertices, that is $\overrightarrow{C}^{p,\gamma _1n+p \ldots ,\gamma _{d-1}n+p}_{\beta n}$ where $p,\gamma _1,\ldots ,\gamma _{d-1},\beta ,n$ are positive integers. This partially answers an open question posed in [2] by simplifying the formula given in [2, Corollary 1].

In the second section we calculate the number of spanning trees in the nth and $(n-1)$th power graphs of the $\beta n$-cycle which are circulant graphs generated by the n, respectively $n-1$, first consecutive integers, denoted by $\varvec{C}^n_{\beta n}$ and $\varvec{C}^{n-1}_{\beta n}$ respectively, where $\beta \in \mathbb {N}_{\geqslant 2}$. As a consequence, the asymptotic behaviour of it is derived. Cycle power graphs appear, for example, in graph colouring problems, see [9, 10].

The results obtained here are derived from the matrix tree theorem (see [1, 4]) which provides a closed formula of a product of $\beta n-1$ terms for a graph on $\beta n$ vertices. Our formulas are products of $\lceil \beta /2\rceil -1$ terms and are therefore interesting when n is large. In both cases, the symmetry of the graphs is reflected in the formulas which are expressed in terms of eigenvalues of subgraphs of the original graph. This fact was already observed in [12].

2 Spanning trees in directed circulant graphs

Let G be a directed graph and V(G) its vertex set. A spanning arborescence converging to $v\in V(G)$ is an oriented subgraph of G such that the out-degree of all vertices except v equals one, and the out-degree of v is zero. We define the combinatorial Laplacian of a directed graph G as an operator acting on the space of functions defined on V(G), by

$$\begin{aligned} \Delta ^-_Gf(x)=\sum _ {y:\ x\rightarrow y}(f(x)-f(y)) \end{aligned}$$

(1)

where the sum is over all vertices y such that there is an oriented edge from x to y. Equivalently, the combinatorial Laplacian can be defined as a matrix by $\Delta ^{-}_{G}=D^{-}-A$, where $D^{-}$ is the out-degree matrix and A is the adjacency matrix such that $(A)_{ij}$ is the number of directed edges from i to j. Let $\tau ^{-}(G,v)$ denote the number of arborescences converging to v. The Tutte matrix tree theorem (see [1]) states that for all $v\in V(G)$,

$$\begin{aligned} \tau ^{-}(G,v)=\det \Delta ^{-}_{G,v} \end{aligned}$$

where ${\det {\Delta }}^{-}_{G,v}$ is the vth cofactor of the Laplacian $\Delta ^{-}_G$ obtained by deleting the row and column of $\Delta ^{-}_G$ corresponding to the vertex v. For a regular directed graph G, we define the number of spanning trees in G, $\tau (G)$, by the sum over all vertices $v\in V(G)$ of the number of arborescences converging to v, that is

$$\begin{aligned} \tau (G)=\sum _{v\in V(G)}\tau ^{-}{(G,v)}. \end{aligned}$$

Fig. 1

Examples of directed graphs

Notice that we could have defined the number of spanning trees by the sum over all vertices $v\in V(G)$ of the number of spanning arborescences diverging from v. By symmetry, all cofactors of the Laplacian of a directed circulant graph are equal and are equal to the product of the non-zero eigenvalues of the Laplacian divided by the number of vertices. Therefore we have that

$$\begin{aligned} \tau (G)=\prod _{k=1}^{|V(G)|}\lambda _k \end{aligned}$$

where $\lambda _k$, $k=1,\ldots ,|V(G)|$, denote the non-zero eigenvalues of the Laplacian of G. The non-zero eigenvalues of the Laplacian of the directed circulant graph $\overrightarrow{C}^{\gamma _1,\ldots ,\gamma _d}_n$ are given by (see [4, Proposition 3.5])

$$\begin{aligned} \lambda _{k}=d-\sum _{m=1}^{d}e^{2\pi i\gamma _mk/n},\quad k=1,\ldots ,n-1. \end{aligned}$$

This can also be derived by noticing that the eigenvectors are given by the characters $\chi _k(x)=e^{2\pi ikx/n}$, $k=0,1,\ldots ,n-1$, and then applying the Laplacian (1) on it.

In this section, we establish a formula for the number of spanning trees in directed circulant graphs $\overrightarrow{C}^\Gamma _{\beta n}$ generated by $\Gamma =\{p,\gamma _1n+p,\ldots ,\gamma _{d-1}n+p\}$ and in the particular case of two generators $\overrightarrow{C}^{p,\gamma n+p}_{\beta n}$. Figure 1 illustrates a 2- and a 3-generated directed circulant graph. We denote by $\mu _k=d-1-\sum \nolimits _{m=1}^{d-1}e^{2\pi i\gamma _mk/\beta }$, $k=1,\ldots ,\beta -1$, the non-zero eigenvalues of the Laplacian on the directed circulant graph $\overrightarrow{C}^{\gamma _1,\ldots ,\gamma _{d-1}}_\beta$ and by $\eta _k=2(d-1)-2\sum \nolimits _{m=1}^{d-1}\cos (2\pi \gamma _mk/\beta )$, $k=1,\ldots ,\beta -1$, the non-zero eigenvalues of the Laplacian on the circulant graph $C^{\gamma _1,\ldots ,\gamma _{d-1}}_\beta$. Let A be a statement and $\delta _A$ be defined by

$$\begin{aligned} \delta _A=\left\{ \begin{array}{ll}1&{}\quad if A is \;satisfied \\ 0&{} \quad otherwise \end{array}.\right. \end{aligned}$$

Theorem 1

Let$1\leqslant \gamma _1\leqslant \cdots \leqslant \gamma _{d-1}\leqslant \beta$ and p, n be positive integers. For all even $n\in \mathbb {N}_{\geqslant 2}$ such that $(p,n)=1$, the number of spanning trees in the directed circulant graph $\overrightarrow{C}^{\Gamma }_{\beta n}$, where $\Gamma =\{p,\gamma _1n+p,\ldots ,\gamma _{d-1}n+p\}$, is given by

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n})= & {} nd^{\beta n-1}\left( 1-\delta _{\beta even }\frac{(-1)^p}{d^n}\left( 1+\sum _{m=1}^{d-1}(-1)^{\gamma _m}\right) ^n\right) \\&\times \prod _{k=1}^{\lceil \beta /2\rceil -1}\Bigg (1-2\Big |1-\frac{\mu _k}{d}\Big |^n\cos \left( \frac{2\pi pk}{\beta }+n{{\mathrm{Arctg}}}\left( \frac{\sum _{m=1}^{d-1}\sin (2\pi \gamma _mk/\beta )}{d-\eta _k/2}\right) \right) \\&\;+\,\Big |1-\frac{\mu _k}{d}\Big |^{2n}\Bigg ) \end{aligned}$$

and for odd $n\in \mathbb {N}_{\geqslant 1}$,

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n})= & {} nd^{\beta n-1}\left( 1-\delta _{\beta even }\frac{(-1)^p}{d^n}\left( 1+\sum _{m=1}^{d-1}(-1)^{\gamma _m}\right) ^n\right) \\&\times \prod _{k=1}^{\lceil \beta /2\rceil -1}\Bigg (1-2\! sgn (d-\eta _k/2)\Big |1-\frac{\mu _k}{d}\Big |^n\cos \left( \frac{2\pi pk}{\beta }\right. \\&\;\left. +\,n{{\mathrm{Arctg}}}\left( \frac{\sum _{m=1}^{d-1}\sin (2\pi \gamma _mk/\beta )}{d-\eta _k/2}\right) \right) +\Big |1-\frac{\mu _k}{d}\Big |^{2n}\Bigg ) \end{aligned}$$

where $\lceil x\rceil$ is the smallest integer greater or equal to x, $|.|$ denotes the modulus and we set $sgn (0)=1$. The number of spanning trees in $\overrightarrow{C}^{\Gamma }_{\beta n}$ is zero if either $(p,n)=1$ and $\beta$, p, $\gamma _m$, $m=1,\ldots ,d-1$ are all even or $(p,n)\ne 1$.

Proof

From the Tutte matrix tree theorem, the number of spanning trees in $\overrightarrow{C}^\Gamma _{\beta n}$ is given by

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n}) =\prod _{k=1}^{\beta n-1}\left( d-e^{2\pi ipk/(\beta n)}-\sum _{m=1}^{d-1}e^{2\pi i(\gamma _mn+p)k/(\beta n)}\right) . \end{aligned}$$

By splitting the product over $k=1,\ldots ,\beta n-1$ into two products, when k is a multiple of $\beta$, that is $k=l\beta$ with $l=1,\ldots ,n-1$, and over non-multiples of $\beta$, that is, $k=k'+l'\beta$ with $k'=1,\ldots ,\beta -1$ and $l'=0,1,\ldots ,n-1$, we have

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n})=\prod _{l=1}^{n-1}(d-de^{2\pi ipl/n})\prod _{k=1}^{\beta -1}\prod _{l'=0}^{n-1}\left( d-\left( 1+\sum _{m=1}^{d-1}e^{2\pi i\gamma _mk/\beta }\right) e^{2\pi ipk/(\beta n)}e^{2\pi ipl'/n}\right) . \end{aligned}$$

(2)

We have that

$$\begin{aligned} \prod _{l=1}^{n-1}(d-de^{2\pi ipl/n})=d^{n-1}\prod _{l=1}^{n-1}(1-e^{2\pi ipl/n})=nd^{n-1}\delta _{(p,n)=1}. \end{aligned}$$

This equality comes from the fact that $\prod \nolimits _{l=1}^{n-1}(1-e^{2\pi ipl/n})$ is the number of spanning trees of the directed graph $\overrightarrow{C}^p_n$, which is isomorphic to the directed cycle on n vertices if $(p,n)=1$, and is not connected if $(p,n)\ne 1$. Therefore the product is equal to $n\delta _{(p,n)=1}$. Hence, if $(p,n)\ne 1$, we have

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n})=0. \end{aligned}$$

Let p be relatively prime to n. Using that the complex numbers $e^{2\pi il/n}$, $l=0,1,\ldots ,n-1$, are the n non-trivial roots of unity, we have for all x,

$$\begin{aligned} \prod _{l=0}^{n-1}(x-e^{2\pi ilp/n})=x^n-1. \end{aligned}$$

(3)

since $(p,n)=1$. Equivalently we have,

$$\begin{aligned} \prod _{l=0}^{n-1}(1-xe^{2\pi ilp/n})=1-x^n. \end{aligned}$$

Using this identity in (2) enables to evaluate the product over $l'$, hence

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n})=nd^{\beta n-1}\prod _{k=1}^{\beta -1}\left( 1-\frac{1}{d^n}\left( 1+\sum _{m=1}^{d-1}e^{2\pi i\gamma _mk/\beta }\right) ^ne^{2\pi ipk/\beta }\right) . \end{aligned}$$

(4)

For odd $\beta$ we write the product over k, $k=1,\ldots ,\beta -1$, as a product from 1 to $(\beta -1)/2$, and for even $\beta$ we write it as a product from 1 to $\beta /2-1$ and add the $k=\beta /2$ factor which is given by $1-(-1)^p(1+\sum \nolimits _{m=1}^{d-1}(-1)^{\gamma _m})^n/d^n$. Writing the above expression in terms of $\mu _k=d-1-\sum \nolimits _{m=1}^{d-1}e^{2\pi i\gamma _mk/\beta }$ yields

$$\begin{aligned} \tau (\overrightarrow{C}^{\Gamma }_{\beta n})= & {} nd^{\beta n-1}\left( 1-\delta _{\beta even }\frac{(-1)^p}{d^n}\left( 1+\sum _{m=1}^{d-1}(-1)^{\gamma _m}\right) ^n\right) \nonumber \\&\times \prod _{k=1}^{\lceil \beta /2\rceil -1}\Big (1-(1-\mu _k/d)^ne^{2\pi ipk/\beta }\Big )\Big (1-(1-\mu _k^*/d)^ne^{-2\pi ipk/\beta }\Big )\nonumber \\= & {} nd^{\beta n-1}\left( 1-\delta _{\beta even }\frac{(-1)^p}{d^n}\left( 1+\sum _{m=1}^{d-1}(-1)^{\gamma _m}\right) ^n\right) \nonumber \\&\times \prod _{k=1}^{\lceil \beta /2\rceil -1}\Big (1-2|1-\mu _k/d|^n\cos (2\pi pk/\beta +n\phi _k)+|1-\mu _k/d|^{2n}\Big )\nonumber \\ \end{aligned}$$

(5)

where $\phi _k$ is the phase of the complex number $1-\mu _k/d$ such that $1-\mu _k/d=|1-\mu _k/d|e^{i\phi _k}$ and $\mu _k^*$ denotes the complex conjugate of $\mu _k$. We have

$$\begin{aligned} |1-\mu _k/d|=\frac{1}{d}\left( (d-\eta _k/2)^2+\left( \sum _{m=1}^{d-1}\sin (2\pi \gamma _mk/\beta )\right) ^2\right) ^{1/2} \end{aligned}$$

and

$$\begin{aligned} \cos {\phi _k}=\frac{d-\eta _k/2}{|d-\mu _k|},\quad \sin {\phi _k}=\frac{\sum \nolimits _{m=1}^{d-1}\sin (2\pi \gamma _mk/\beta )}{|d-\mu _k|}. \end{aligned}$$

Therefore for k such that $d-\eta _k/2\ne 0$, the phase is given by

$$\begin{aligned} \phi _k={{\mathrm{Arctg}}}\left( \frac{\sum \nolimits _{m=1}^{d-1}\sin (2\pi \gamma _mk/\beta )}{d-\eta _k/2}\right) +\epsilon \pi \end{aligned}$$

(6)

where $\epsilon =0$ if $sgn (d-\eta _k/2)=1$ and $\epsilon \in \{-1,1\}$ if $sgn (d-\eta _k/2)=-1$. For k such that $d-\eta _k/2=0$, we take the limit as $d-\eta _k/2\rightarrow 0$ in (6), with $\epsilon =0$. The theorem follows by putting Eq. (6) into Eq. (5).

When $\beta$, p and $\gamma _m$, $m=1,\ldots ,d-1$, are all even, the directed circulant graph $\overrightarrow{C}^{\Gamma }_{\beta n}$ is not connected and therefore the number of spanning trees is zero, this is reflected in the formula. $\square$

In the following corollary we state the particular case of 2-generated directed circulant graphs.

Corollary 1

Let $1\leqslant \gamma \leqslant \beta$ and p, n be positive integers. For odd $\beta$ and all $n\in \mathbb {N}_{\geqslant 1}$ such that $(p,n)=1$, the number of spanning trees in the directed circulant graph $\overrightarrow{C}^{p,\gamma n+p}_{\beta n}$ is given by

$$\begin{aligned}&\tau (\overrightarrow{C}^{p,\gamma n+p}_{\beta n})\\&\quad =n2^{\beta n-1}\prod _{k=1}^{(\beta -1)/2}\Big (1-2\cos (2\pi (p+\gamma n/2)k/\beta )\cos ^n(\pi \gamma k/\beta )+\cos ^{2n}(\pi \gamma k/\beta )\Big ) \end{aligned}$$

and for even $\beta$, if $\gamma$ or p is odd, then

$$\begin{aligned}&\tau (\overrightarrow{C}^{p,\gamma n+p}_{\beta n})\\&\quad =n2^{\beta n-1+\delta _{\gamma even }}\prod _{k=1}^{\beta /2-1}\Big (1-2\cos (2\pi (p+\gamma n/2)k/\beta )\cos ^n(\pi \gamma k/\beta )+\cos ^{2n}(\pi \gamma k/\beta )\Big ). \end{aligned}$$

The number of spanning trees in $\overrightarrow{C}^{p,\gamma n+p}_{\beta n}$ is zero if either $(p,n)=1$ and $\beta$, p and $\gamma$ are all even or $(p,n)\ne 1$.

Proof

From Eq. (4) it follows

$$\begin{aligned} \tau (\overrightarrow{C}^{p,\gamma n+p}_{\beta n})=n2^{\beta n-1}\prod _{k=1}^{\beta -1}\Big (1-e^{2\pi i(p+\gamma n/2)k/\beta }\cos ^n(\pi \gamma k/\beta )\Big ). \end{aligned}$$

For odd $\beta$, we have

$$\begin{aligned} \tau (\overrightarrow{C}^{p,\gamma n+p}_{\beta n})= & {} n2^{\beta n-1}\prod _{k=1}^{(\beta -1)/2}\Big (1-e^{2\pi i(p+\gamma n/2)k/\beta }\cos ^n(\pi \gamma k/\beta )\Big )\\&\times \Big (1-e^{-2\pi i(p+\gamma n/2)k/\beta }\cos ^n(\pi \gamma k/\beta )\Big )\\= & {} n2^{\beta n-1}\prod _{k=1}^{(\beta -1)/2}\Big (1-2\cos (2\pi (p+\gamma n/2)k/\beta )\cos ^n(\pi \gamma k/\beta )+\cos ^{2n}(\pi \gamma k/\beta )\Big ). \end{aligned}$$

For even $\beta$, the factor $k=\beta /2$ is added:

$$\begin{aligned} 1-e^{\pi i(p+\gamma n/2)}\cos ^n(\pi \gamma /2)=\left\{ \begin{array}{ll}0&{}\quad if \;p\; and \;\gamma \; are even \\ 1&{}\quad if\; \gamma \; is\; odd \\ 2&{}\quad otherwise \end{array}.\right. \end{aligned}$$

For even $\beta$, p and $\gamma$, the graph $\overrightarrow{C}^{p,\gamma n+p}_{\beta n}$ is not connected and therefore the number of spanning trees is zero. If p or $\gamma$ is odd, we have

$$\begin{aligned} \tau (\overrightarrow{C}^{p,\gamma n+p}_{\beta n})= & {} n2^{\beta n-1+\delta _{\gamma even }}\prod _{k=1}^{\beta /2-1}\Big (1-e^{2\pi i(p+\gamma n/2)k/\beta }\cos ^n(\pi \gamma k/\beta )\Big )\\&\times \Big (1-e^{-2\pi i(p+\gamma n/2)k/\beta }\cos ^n(\pi \gamma k/\beta )\Big )\\= & {} n2^{\beta n-1+\delta _{\gamma even }}\prod _{k=1}^{\beta /2-1}\Big (1-2\cos (2\pi (p+\gamma n/2)k/\beta )\cos ^n(\pi \gamma k/\beta )+\cos ^{2n}(\pi \gamma k/\beta )\Big ). \end{aligned}$$

$\square$

Example 1

Consider the case when $p=\beta =3$ and $\gamma =2$. It follows from Theorem 1 that $\tau (\overrightarrow{C}^{3,2n+3}_{3n})=0$ if n is a multiple of 3, otherwise,

$$\begin{aligned} \tau (\overrightarrow{C}^{3,2n+3}_{3n})= & {} n2^{3n-1}\big (1-2\cos (2\pi n/3)\cos ^n(2\pi /3)+\cos ^{2n}(2\pi /3)\big )\\= & {} n\big (2^{3n-1}-2^{2n}\cos (\pi n/3)+2^{n-1}\big ) \end{aligned}$$

as stated in [13, Example 4. (iii)]. As another example, consider the case when $p=2$, $\gamma =5$ and $\beta =6$. From Theorem 1, for even n, $\tau (\overrightarrow{C}^{2,5n+2}_{6n})=0$, and for odd n,

$$\begin{aligned} \tau (\overrightarrow{C}^{2,5n+2}_{6n})= & {} n2^{6n-1}\big (1-2\cos (2\pi (2+5n/2)/6)\cos ^n(5\pi /6)+\cos ^{2n}(5\pi /6)\big )\\&\times \big (1-2\cos (4\pi (2+5n/2)/6)\cos ^n(10\pi /6)+\cos ^{2n}(10\pi /6)\big )\\= & {} \frac{n}{2}\big (2^{3n}+2^{2n}3^{n/2}\cos (\pi n/6)-2^{2n}3^{(n+1)/2}\sin (\pi n/6)+6^n\big )\\&\times \big (2^{3n}-2^{2n-1}3^{n/2}\cos (\pi n/3)+2^{n-1}3^{(n+1)/2}\sin (\pi n/3)+2^n\big ). \end{aligned}$$

3 Spanning trees in cycle power graphs

The kth power graph of the n-cycle, denoted by $\varvec{C}^k_n$, is the graph with the same vertex set as the n-cycle where two vertices are connected if their distance on the n-cycle is at most k. It is thus the circulant graph on n vertices generated by the first k consecutive integers. In this section, we derive a formula for the number of spanning trees in the nth and $(n-1)$th power graph of the $\beta n$-cycle, where $\beta \in \mathbb {N}_{\geqslant 2}$. As a consequence we derive the asymptotic behaviour of it as n goes to infinity. The combinatorial Laplacian of an undirected graph G with vertex set V(G) defined as an operator acting on the space of functions on V(G) is

$$\begin{aligned} \Delta _Gf(x)=\sum _{y\sim x}(f(x)-f(y)) \end{aligned}$$

where the sum is over all vertices adjacent to x. The matrix tree theorem [4] states that the number of spanning trees in G, $\tau (G)$, is given by

$$\begin{aligned} \tau (G)=\frac{\prod _{k=1}^{|V(G)|-1}\lambda _k}{|V(G)|} \end{aligned}$$

where $\lambda _k$, $k=1,\ldots ,|V(G)|-1$, are the non-zero eigenvalues of $\Delta _G$. The eigenvectors of the Laplacian on the circulant graph $C^{1,\ldots ,n}_{\beta n}$ are given by the characters $\chi _k(x)=e^{2\pi ikx/(\beta n)}$, $k=0,1,\ldots ,\beta n-1$. Therefore the non-zero eigenvalues are given by

$$\begin{aligned} \lambda _k=2n-2\sum _{m=1}^n\cos (2\pi km/(\beta n)),\quad k=1,\ldots ,\beta n-1. \end{aligned}$$

Similarly, the non-zero eigenvalues on $C^{1,\ldots ,n-1}_{\beta n}$ are given by

$$\begin{aligned} \lambda _k=2(n-1)-2\sum _{m=1}^{n-1}\cos (2\pi km/(\beta n)),\quad k=1,\ldots ,\beta n-1. \end{aligned}$$

Fig. 2

8th and 7th power graphs of the 24cycle

Figure 2 below illustrates two power graphs of the 24-cycle.

Theorem 2

Let $\beta \geqslant 2$ be an integer and $\mu _k=2-2\cos (2\pi k/\beta )$, $k=1,\ldots ,\beta -1$, be the non-zero eigenvalues of the Laplacian on the $\beta$-cycle. The number of spanning trees in the nth power graph of the $\beta n$-cycle $\varvec{C}^n_{\beta n}$ for $\beta \geqslant 3$, is given by

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})= & {} \frac{2^{\beta (n+1)}}{(2\beta )^2}n^{\beta n-2}\left( 1+\frac{1}{2n}\right) ^{\beta n}(1-(2n+1)^{-\beta })^n\\&\times \prod _{k=1}^{\lceil \beta /2\rceil -1}\sin ^2\left( \frac{\pi (n+1)k}{\beta }-n{{\mathrm{Arcsin}}}\left( \frac{n+1}{\sqrt{4n^2/\mu _k+2n+1}}\right) \right) \end{aligned}$$

where $\lceil x\rceil$ denotes the smallest integer greater or equal to x. For $\beta =2$, it is given by

$$\begin{aligned} \tau (\varvec{C}^n_{2n})=(2n)^{2n-2}(1+1/n)^n. \end{aligned}$$

The number of spanning trees in the $(n-1)$th power graph of the $\beta n$-cycle $\varvec{C}^{n-1}_{\beta n}$, for $\beta \geqslant 3$, is given by

$$\begin{aligned} \tau (\varvec{C}^{n-1}_{\beta n})= & {} \frac{2^{\beta (n+1)}}{(2\beta )^2}n^{\beta n-2}\left( 1-\frac{1}{2n}\right) ^{\beta n}|(-1)^\beta -(2n-1)^{-\beta }|^n\\&\times \prod _{k=1}^{\lceil \beta /2\rceil -1}\sin ^2\left( \frac{\pi (n-1)k}{\beta }-n{{\mathrm{Arcsin}}}\left( \frac{n-1}{\sqrt{4n^2/\mu _k-(2n-1)}}\right) \right) . \end{aligned}$$

For $\beta =2$, it is given by

$$\begin{aligned} \tau (\varvec{C}^{n-1}_{2n})=(2n)^{2n-2}(1-1/n)^n. \end{aligned}$$

Remark 1

We emphasise that in the cycle power graphs $\varvec{C}^{n-1}_{\beta n}$ and $\varvec{C}^n_{\beta n}$ there are $\beta$ copies of n-cliques as subgraphs of the original graph. This fact appears in the formula by the factor $n^{\beta n-2}=(n^{n-2})^\beta n^{2(\beta -1)}$ since the number of spanning trees in the complete graph on n vertices is $n^{n-2}$.

Proof

We prove the theorem only for the first type of graphs $\varvec{C}^n_{\beta n}$. The proof of the second type $\varvec{C}^{n-1}_{\beta n}$ is very similar to the first one. The matrix tree theorem states that

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})=\frac{1}{\beta n}\prod _{k=1}^{\beta n-1} \Big (2n-2\sum _{m=1}^n\cos (2\pi km/(\beta n))\Big ). \end{aligned}$$

Lagrange’s trigonometric identity expresses the sum of cosines appearing in the above formula in terms of a quotient of sines:

$$\begin{aligned} 2\sum _{m=1}^n\cos (2\pi km/(\beta n))=\frac{\sin ((n+1/2)2\pi k/(\beta n))}{\sin (\pi k/(\beta n))}-1. \end{aligned}$$

Hence,

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})=\frac{1}{\beta n}\prod _{k=1}^{\beta n-1}\big (\sin (\pi k/(\beta n))\big )^{-1}\Big ((2n+1)\sin (\pi k/(\beta n))-\sin (\pi k/(\beta n)+2\pi k/\beta )\Big ). \end{aligned}$$

Using that there are $\beta n$ spanning trees in the $\beta n$-cycle, that is $\frac{1}{\beta n}\prod _{k=1}^{\beta n-1}(2-2\cos (2\pi k/(\beta n)))=\beta n$, it follows that

$$\begin{aligned} \prod _{k=1}^{\beta n-1}\sin (\pi k/(\beta n))=\frac{\beta n}{2^{\beta n-1}}. \end{aligned}$$

(7)

For the second factor, as in the proof of Theorem 1, we split the product over $k=1,\ldots ,\beta n-1$ into two products, first when k is a multiple of $\beta$, that is $k=l\beta$ with $l=1,\ldots ,n-1$, and second when k is not a multiple of $\beta$, that is, $k=k'+l'\beta$ with $k'=1,\ldots ,\beta -1$ and $l'=0,1,\ldots ,n-1$. The product over the multiples of $\beta$ reduces to

$$\begin{aligned} \prod _{l=1}^{n-1}2n\sin (\pi l/n)=n^n. \end{aligned}$$

We have

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})=\frac{2^{\beta n-1}n^n}{(\beta n)^2}\prod _{k=1}^{\beta -1}\prod _{l=0}^{n-1}\Big ((2n+1)\sin (\pi k/(\beta n)+\pi l/n)-\sin (\pi k/(\beta n)+\pi l/n+2\pi k/\beta )\Big ). \end{aligned}$$

(8)

The difference of sines in the above product can be written as

$$\begin{aligned}&(2n+1)\sin (\pi k/(\beta n)+\pi l/n)-\sin (\pi k/(\beta n)+\pi l/n+2\pi k/\beta )\nonumber \\&\quad ={|} z_{k}{|}\sin (\pi (n+1)k/(\beta n)+\theta _{k}+\pi l/n) \end{aligned}$$

(9)

where

$$\begin{aligned} z_k=2n\cos (\pi k/\beta )-i(2n+2)\sin (\pi k/\beta )=:|z_k|e^{i\theta _k}. \end{aligned}$$

Let $\omega _k=\pi (n+1)k/(\beta n)+\theta _k$, we have

$$\begin{aligned} \prod _{l=0}^{n-1}\sin (\omega _k+\pi l/n)= & {} \frac{1}{(2i)^n}\prod _{l=0}^{n-1}(e^{i(\omega _k+\pi l/n)}-e^{-i(\omega _k+\pi l/n)})\nonumber \\= & {} \frac{1}{(2i)^n}e^{-i\omega _kn}e^{\pi i(n-1)/2}\prod _{l=0}^{n-1}(e^{2i\omega _k}-e^{-2\pi il/n})\nonumber \\= & {} \frac{\sin (\omega _kn)}{2^{n-1}} \end{aligned}$$

(10)

where in the last equality we used Eq. (3). Putting Eqs. (8), (9) and (10) together yields

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})=\frac{2^{\beta n-1}n^n}{(\beta n)^2}\prod _{k=1}^{\beta -1}\frac{|z_k|^n}{2^{n-1}}\sin (\pi (n+1)k/\beta +n\theta _k). \end{aligned}$$

Notice that for even $\beta$, the phase of $z_{\beta /2}$ is $\theta _{\beta /2}=-\pi /2$, so that $\sin (\pi (n+1)/2+n\theta _{\beta /2})=1$. For $\beta =2$, $z_1=-2(n+1)i$, hence

$$\begin{aligned} \tau (\varvec{C}^n_{2n})=(2n)^{2n-2}(1+1/n)^n. \end{aligned}$$

For $\beta \geqslant 3$, we have

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})= & {} \frac{2^{n+\beta -2}n^n}{(\beta n)^2}\left( \prod _{k=1}^{\beta -1}|z_k|^n\right) \prod _{k=1}^{\lceil \beta /2\rceil -1}\\&\sin (\pi (n+1)k/\beta +n\theta _k)\sin (\pi (n+1)(\beta -k)/\beta +n\theta _{\beta -k}). \end{aligned}$$

For $1\leqslant k\leqslant \lceil \beta /2\rceil -1$, the phase of $z_k$ is $\theta _k=-{{\mathrm{Arcsin}}}((2n+2)\sin (\pi k/\beta )/|z_k|)$. The phase of $z_{\beta -k}$ satisfies

$$\begin{aligned} \cos \theta _{\beta -k}=-\cos \theta _k,\quad \sin \theta _{\beta -k}=\sin \theta _k \end{aligned}$$

so that, $\theta _{\beta -k}=\pi -\theta _k$. The modulus of $z_k$ is given by

$$\begin{aligned} |z_k|=\big ((2n+1)^2+1-2(2n+1)\cos (2\pi k/\beta )\big )^{1/2}=(4n^2+(2n+1)\mu _k)^{1/2} \end{aligned}$$

where $\mu _k=2-2\cos (2\pi k/\beta )$, $k=1,\ldots ,\beta -1$, are the non-zero eigenvalues of the Laplacian on the $\beta$-cycle. We have $\sin (\pi k/\beta )=\mu _k^{1/2}/2$. Hence for $1\leqslant k\leqslant \lceil \beta /2\rceil -1$, the phase is given by $\theta _k=-{{\mathrm{Arcsin}}}((n+1)/\sqrt{4n^2/\mu _k+2n+1})$. Therefore

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})= & {} \frac{2^{n+\beta -2}n^n}{(\beta n)^2}\bigg (\prod _{k=1}^{\beta -1}|z_k|^n\bigg )\prod _{k=1}^{\lceil \beta /2\rceil -1}\sin ^2\left( \frac{\pi (n+1)k}{\beta }\right. \nonumber \\&\left. -\,n{{\mathrm{Arcsin}}}\left( \frac{n+1}{\sqrt{4n^2/\mu _k+2n+1}}\right) \right) . \end{aligned}$$

(11)

The product of the modulus of $z_k$ is given by

$$\begin{aligned} \prod _{k=1}^{\beta -1}|z_k|= & {} \frac{(2n+1)^{\beta /2}}{2n}\prod _{k=0}^{\beta -1}(2n+1+1/(2n+1)-2\cos (2\pi k/\beta ))^{1/2}\nonumber \\= & {} \frac{(2n+1)^{\beta /2}}{2n}\Big (2\cosh \big (\beta {{\mathrm{Argcosh}}}(n+1/2+1/(4n+2))\big )-2\Big )^{1/2}\nonumber \\= & {} \frac{(2n+1)^{\beta }}{2n}(1-(2n+1)^{-\beta }) \end{aligned}$$

(12)

where the second equality comes from the identity (see [12, section 2])

$$\begin{aligned} \prod _{k=0}^{\beta -1}(2\cosh \theta -2\cos (2\pi k/n))=2\cosh ({\beta }{\theta })-2. \end{aligned}$$

Putting equality (12) into (11) gives the theorem. $\square$

Remark 2

We point out that the proof above could not be easily applied to other powers of the $\beta n$-cycle, like $\varvec{C}^{n-p}_{\beta n}$, where $p\geqslant 2$ or $p\leqslant -1$, because in this case $z_k$ defined in Eq. (9) would also depend on l and the phase $\theta _k$ of $z_k$ cannot be easily determined. As a consequence, the product over l cannot be evaluated in the same way as it is done in the proof. It would be interesting to find a derivation in this class of more general circulant graphs.

From Theorem 2, we derive the asymptotic behaviour of the number of spanning trees in the nth, respectively $(n-1)$th, power graph of the $\beta n$-cycle as $n\rightarrow \infty$.

Corollary 2

Let $\beta \in \mathbb {N}_{\geqslant 2}$. The asymptotic numbers of spanning trees in the nth and $(n-1)$th power graphs of the $\beta n$-cycle $\varvec{C}^n_{\beta n}$ and $\varvec{C}^{n-1}_{\beta n}$ as $n\rightarrow \infty$ are respectively given by

$$\begin{aligned} \tau (\varvec{C}^n_{\beta n})=\frac{2^{\beta (n+1)}}{(2\beta )^2}n^{\beta n-2}\prod _{k=1}^{\lceil \beta /2\rceil -1}\sin ^2\Big (\pi k/\beta -\sin (2\pi k/\beta )/2\Big )(e^{\beta /2}+o(1)) \end{aligned}$$

and

$$\begin{aligned} \tau (\varvec{C}^{n-1}_{\beta n})=\frac{2^{\beta (n+1)}}{(2\beta )^2}n^{\beta n-2}\prod _{k=1}^{\lceil \beta /2\rceil -1}\sin ^2\Big (\pi k/\beta -\sin (2\pi k/\beta )/2\Big )(e^{-\beta /2}+o(1)). \end{aligned}$$

Proof

By observing that for all $k\in \{1,\ldots ,\lceil \beta /2\rceil -1\}$ and for large n,

$$\begin{aligned} {{\mathrm{Arcsin}}}\left( \frac{n+1}{\sqrt{4n^2/\mu _k+2n+1}}\right) =\pi k/\beta +\frac{1}{2n}\sin (2\pi k/\beta )+O(n^{-2}) \end{aligned}$$

and

$$\begin{aligned} {{\mathrm{Arcsin}}}\left( \frac{n-1}{\sqrt{4n^2/\mu _k-(2n-1)}}\right) =\pi k/\beta -\frac{1}{2n}\sin (2\pi k/\beta )+O(n^{-2}) \end{aligned}$$

where $\mu _k=2-2\cos (2\pi k/\beta )$, the corollary is a direct consequence of Theorem 2. $\square$