# The Number of Spanning Trees of the Cartesian Product of Regular Graphs

Authors: Mei-Hui Wu; Long-Yeu Chung
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The number of spanning trees in graphs or in networks is an important issue. The evaluation of this number not only is interesting from a mathematical (computational) perspective but also is an important measure of reliability of a network or designing electrical circuits. In this paper, a simple formula for the number of spanning trees of the Cartesian product of two regular graphs is investigated. Using this formula, the number of spanning trees of the four well-known regular networks can be simply taken into evaluation.


---

## Body

## 1. Introduction

In this paper, we deal with simple undirected graphs having no self-loop or multiple edges and consider the Cartesian product of two regular graphs only. It is well known that, for designing large-scale interconnection networks, the Cartesian product is an important method to obtain large networks from smaller ones, with a number of parameters that can be easily calculated from the corresponding parameters for those small initial graphs. The Cartesian product preserves many nice properties such as regularity, transitivity, super edge-connectivity, and super point-connectivity of the initial regular graphs [1–6]. In fact, many well-known networks can be constructed by the Cartesian products of simple regular graphs, for example, Boolean n-cube networks, hypercube networks, and lattice networks.Alternatively, the study of the number of spanning trees in a graph has a long history and has been very active because the problem has different practical applications in different fields. For example, the number characterizes the reliability of a network and, in physics, designing electrical circuits, analyzing energy of masers, and investigating the possible particle transitions [7–10]. The larger degree of points a network has, the more I/O ports and edges are needed and the more cost is required.The number of spanning trees of some special network has been taken into evaluation [11–20]. Recently, some authors derived results about the counting where the number of spanning trees can be found from [21–29]. However, the study for spanning trees of the Cartesian product of regular graphs remains an open and important invariant.The number of spanning trees of Booleann-cube networks, lattice networks, and generalized Boolean n-cube networks has been taken into account [13, 17, 18]; these networks belong to the class of networks Qn with two regular graphs Q1 and G which is defined recursively by Qn=Qn-1×G for n≥2. In this paper, we will present the formula of the number of spanning trees of the Cartesian product of regular graphs. Using this present formula, the main results in [13, 17, 18] can be obtained much more simply and will be extended.


## 2. The Number of Spanning Trees

Definition 1.
LetG be a graph with n points labeled 1,2,…,n. The adjacency matrix of G,A(G), is an n×n matrix with the ith row and jth column entry given by(1)[A(G)]ij={1ifpointsiandjareadjacent0ortherwise.
The Kirchhoff matrix of G,H(G), is equal to D(G)-A(G), where D(G) is an n×n diagonal matrix whose diagonal entries are the degree of point n and A(G) is the adjacency matrix. Thus the ith row and jth column entry is given by
(2)[H(G)]ij={deg⁡(i)ifi=j-1ifi≠jandpointsiandjareadjacent0ortherwise.Lemma 2 (see [30]).
IfG is a graph on n points with Kirchhoff matrix H(G) and Hij(G) is the submatrix of H(G) obtained by removing the ith row and jth column then the number of spanning trees of G,  t(G), is any cofactor of H(G). That is, t(G)=(-1)i+jdet⁡(Hij(G)).Lemma 3.
IfA is an n×n triangulable matrix, which has n eigenvalues, then the sum of product of any n-1 eigenvalues of A is the sum of all principal minors of A.Proof.
Letp(λ) be the character polynomial of A and λ1,λ2,…,λn are n eigenvalues of A. Then
(3)p(λ)=(λ-λ1)(λ-λ2)⋯(λ-λn).
From (3), we obtain the following.
(a) The coefficient ofλ=(-1)n-1·(thesumofproductofanyn-1eigenvaulesofA).
On the other hand,(4)p(λ)=det⁡(λI-A)=|λ(1)-a11-a12⋯-a1n-a21λ(2)-a22⋯-a2n⋮⋮⋱⋮-a21-a21⋯λ(n)-ann|,
where A=[aij] and λ(i)=λ for i=1,2,…,n.
So we only need to prove that the coefficient ofλ in det⁡(λI-A) is the sum of all principal minors of A. Let Aii denote the principal minor of A obtained by removing the ith row and ith column from A.
By (4), we obtain the following:(5)thecoefficientofλ(1)=(-1)n-1A11(takingλ(2)=λ(3)=⋯=λ(n)=0)thecoefficientofλ(2)=(-1)n-1A22(takingλ(1)=λ(3)=λ(4)⋯=λ(n)=0)⋮thecoefficientofλ(n)=(-1)n-1Ann(takingλ(1)=λ(2)=⋯=λ(n-1)=0).
(b) So the coefficient ofλ=∑i=1n  the coefficient ofλ(i)=(-1)n-1(A11+A22+⋯+Ann).
Hence the theorem is proved due to (a) and (b).Since a real symmetric matrix is with the property that the sum of its rows (and its columns) is zero, the rank ofH(G)≤n-1. So 0 is the smallest eigenvalue. We write the eigenvalues of H(G) as an ordered list:
(6)0=λ0(G)≤λ1(G)≤λ2(G)⋯≤λn-1(G).
The main result in Kelmans and Chelnokov [31] can also be obtained by the following method.Lemma 4 (see [31]).
If the eigenvalues of the Kirchhoff matrixH(G) of the n points graph G are 0=λ0(G)≤λ1(G)≤λ2(G)⋯≤λn-1(G) then t(G), the number of spanning trees of G, is given by
(7)t(G)=1n∏i=1n-1λi(G).Proof.
By Lemmas2 and 3,
(8)∏i=1n-1λi(G)=thesumofproductofanyn-1eigenvaulesofH(G)=thesumofallprincipalminorsofH(G)=n·t(G).
Hence t(G)=(1/n)∏i=1n-1λi(G).Lemma 5.
Let the eigenvalues of the adjacency matrixA(G) of the regular graph G be written by u1≤u2⋯≤un-1≤un=n, where r is the degree of the regular graph G; then, the number of spanning trees of G is given by
(9)t(G)=1n∏i=1n-1(r-ui).Proof.
We knowH(G)=rIn-A(G), where In is the identity n×n matrix. Since ui is the eigenvalue of A(G) for i=1,2,…,n-1, there exists eigenvector xi for i=1,2,…,n-1, such that A(G)xi=uixi. So (rIn-H(G))xi=uixi,  rInxi-H(G)xi=uixi, rxi-H(G)xi=uixi, and  H(G)xi=rxi-uixi.
We obtainH(G)xi=(r-ui)xi. Thus r-ui is the eigenvalue of H(G) for i=1,2,…,n-1.
Hence the lemma is proved by Lemma4.


## 3. Cartesian Product and Kronecker Product

Definition 6.
LetG=(N,E) denote a connected graph with N set of all points and E set of all edges in G and let {u,v} denote edge joining points u and v. Let Gi=(Ni,Ei) for i=1,2; the Cartesian product of G1 and G2 is defined by G1×G2=(N,E), where N=N1×N2,  E=E1×E2, and {(u1,v1),(u2,v2)}∈E if and only if u1=u2 and {v1,v2}∈E2 or v1=v2 and {u1,u2}∈E1.Definition 7 (see [32]).
LetB=[bij] be an n×n matrix and C an m×m matrix; then, the Kronecker product B×KC is defined as the mn×mn matrix with block description
(10)[b11Cb12C⋯b1nCb21Cb22C⋯b2nC⋮⋮⋱⋮bn1Cbn2C⋯bnnC].
The Kronecker sum is defined by B+KC=B×KIm+In×KC, where Ik is the k×k identity matrix for k=m,n. Let M be an mn×mn matrix. M can be partitioned into n2 blocks which are denoted by Bαβ for α=1,2,…,n and β=1,2,…,n. That is,
(11)M=[B11B12⋯B1nB21B22⋯Bn1⋮⋮⋱⋮Bn1Bn2⋯Bnn],
where Bαβ is the m×m matrix for α=1,2,…,n and  β=1,2,…,n.  M is called an n×n  (m×m) block matrix.Lemma 8.
IfA is an n×n matrix and B, C are m×m matrices then(1)
A×K(B+C)=A×KB+A×KC,(2)
(B+C)×KA=B×KA+C×KA.Proof.
The lemma is easily obtained.Lemma 9.
If the productsAB and CD are defined then (AB)×K(CD)=(A×KC)(B×KD).Proof.
LetA=[aij] be an m×n matrix and B=[bij] an n×p matrix
(12)(A×KC)(B×KD)=[a11C⋯a1nC⋮⋱⋮am1C⋯amnC][b11D⋯b1pD⋮⋱⋮bn1D⋯bnpD]=[∑k=1na1kbk1CD⋯∑k=1na1kbkpCD⋮⋱⋮∑k=1namkbk1CD⋯∑k=1namkbkpCD]=(AB)×K(CD).Lemma 10.
IfP and Q are invertible then (P×KQ)-1=P-1×KQ-1.Proof.
Consider(13)(P×KQ)(P-1×KQ-1)=(PP-1)×K(QQ-1)=Im×KIn=Imn,
where P is m×m and Q is n×n.


## 4. The Number of Spanning Trees of the Cartesian Product of Regular Graphs

Lemma 11.
If the points ofG1 and G2 are labeled by u1,u2,…un and v1,v2,…,vm, respectively, and points of G1×G2 are ordered lexicographically, that is, the label of (ui,vj) is smaller than that of (uk,vl) if and only if i<k and j<l, then A(G1×G2)=A(G1)+KA(G2).Proof.
SinceA(G1×G2) is an mn×mn matrix, A(G1×G2) is an n×n  (m×m) block matrix. By the definition of G1×G2, we describe(14)A(G1×G2)=[A(G2)[A(G1)]12Im[A(G1)]13Im⋯[A(G1)]1,n-1Im[A(G1)]1,nIm[A(G1)]21ImA(G2)[A(G1)]23Im⋯[A(G1)]2,n-1Im[A(G1)]2,nIm⋮⋮⋮⋮⋮[A(G1)]n-1,1Im[A(G1)]n-1,2Im[A(G1)]n-1,3Im⋯A(G2)[A(G1)]n-1,nIm[A(G1)]n,1Im[A(G1)]n,2Im[A(G1)]n,3Im⋯[A(G1)]n,n-1ImA(G2)],
where[A(G1)]ij is the (i,j) entry of the adjacent matrix A(G1) of G1 and A(G2) is the m×m adjacent matrix of G2. We know In×KA(G2) is an mn×mn matrix; it can be described as an n×n(m×m) block matrix(15)In×KA(G2)=[A(G2)0m×m0m×m⋯0m×m0m×m0m×mA(G2)0m×m⋯0m×m0m×m⋮⋮⋮⋯⋮⋮0m×m0m×m0m×m⋯A(G2)0m×m0m×m0m×m0m×m⋯0m×mA(G2)],
where0m×m is the m×m zero matrix. Since A(G1)×KIm is an mn×mn matrix, it can be described as an n×n(m×m) block matrix(16)A(G1)×KIm=[0m×m[A(G1)]12Im[A(G1)]13Im⋯[A(G1)]1,n-1Im[A(G1)]1,nIm[A(G1)]21Im0m×m[A(G1)]23Im⋯[A(G1)]2,n-1Im[A(G1)]2,nIm⋮⋮⋮⋮⋮[A(G1)]n-1,1Im[A(G1)]n-1,2Im[A(G1)]n-1,3Im⋯0m×m[A(G1)]n-1,nIm[A(G1)]n,1Im[A(G1)]n,2Im[A(G1)]n,3Im⋯[A(G1)]n,n-1Im0m×m].
ClearlyA(G1×G2)=A(G1)×KIm+In×KA(G2)=A(G1)+KA(G2).Lemma 12.
LetGi be the regular graph of degree ri for i=1,2; then, the degree of G1×G2 is r1+r2. If the number of the points of G1 (resp., G2) is n (resp., m) and the points of G1×G2 are ordered lexicographically then H(G1×G2)=H(G1)+KH(G2).Proof.
By Lemmas8 and 11,
(17)H(G1×G2)=(r1+r2)Imn-A(G1×G2)=(r1+r2)Imn-(A(G1)+KA(G2))=(r1+r2)Imn-(A(G1)×KIm+In×KA(G2))=(r1Imn-In×KA(G2))+(r2Imn-A(G1)×KIm)=(In×Kr1Im-In×KA(G2))+(r2In×KIm-A(G1)×KIm)=In×K(r1Im-A(G2))+(r2In-A(G1))×KIm=In×KH(G2)+H(G1)×KIm=H(G1)+KH(G2),
where Imm is the mn×mn identity matrix.Lemma 13.
IfA and B are triangulable matrices then the eigenvalues of A+kB are given by α+β, respectively, as α and β vary through the eigenvalues of A and B.Proof.
SinceA and B are triangulable, there exist invertible matrices Q and P such that A1=QAQ-1 and B1=PBP-1 are upper triangular. If A and B are n×n and m×m matrices, respectively, by Lemmas 9 and 10,
(18)A1+kB1=A1×KIm+In×KB1=(QAQ-1)×K(PImP-1)+(QInQ-1)×K(PBP-1)=(Q×KP)(AQ-1×KImP-1)+(Q×KP)(InQ-1×KBP-1)=(Q×KP)(A×KIm)(Q-1×KP-1)+(Q×KP)(In×KB)(Q-1×KP-1)=(Q×KP)[(A×KIm)+(In×KB)](Q-1×KP-1)=(Q×KP)[(A×KIm)+(In×KB)](Q×KP)-1=(Q×KP)(A+kB)(Q×KP)-1.
So A+kB is similar to A1+kB1 and they have the same eigenvalues. Obviously A1+kB1=A1×KIm+In×KB1 is upper triangular with diagonal entries given by α+β, respectively, as α and β vary through the eigenvalues of A1 and B1. Hence the eigenvalues of A+kB are α+β, respectively, as α and β vary through the eigenvalues of A and B.Theorem 14.
LetG1 and G2 be the regular graphs with degrees m and n, respectively. If the eigenvalues of the adjacency matrix A(G1) are written as α1≤α2⋯≤αn-1≤αm=m and the eigenvalues of the adjacency matrix A(G2) are written as β1≤β2⋯≤βn-1≤βn=n, then the number of spanning trees of the Cartesian product G1×G2 is
(19)t(G1×G2)=1mn∏i,j[(m+n)-(αi+βj)],
where i and j satisfy (i,j)∈{1,2,…,m}×{1,2,…,n}-{(m,n)}.Proof.
We knowG1×G2 has mn points and the degree of G1×G2 is m+n. By Lemma 11, A(G1×G2)=A(G1)+KA(G2). By Lemma 13, the eigenvalues of A(G1×G2) are αi+βj for i=1,2,…,m and j=1,2,…,n. The result follows by Lemma 5.Theorem 15.
IfG1 and G2 are the regular graph of degrees m and n, respectively, the eigenvalues of the Kirchhoff matrix H(G1) are written as 0=λ0≤λ1⋯≤λm-1, and the eigenvalues of the Kirchhoff matrix H(G2) are written as 0=γ0≤γ1⋯≤γn-1, then the number of spanning trees of the Cartesian product of G1 and G2 is
(20)t(G1×G2)=1mn∏i,j(λi+γj),
where i and j satisfy (i,j)∈{0,1,…,m-1}×{0,1,…,n-1}-{(0,0)}.Proof.
By Lemma12, H(G1×G2)=H(G1)+KH(G2). By Lemma 13, the eigenvalues of H(G1×G2) are λi+γj for i=0,1,…,m-1 and j=0,1,…,n-1. Hence by Lemma 4, the result follows.


## 5. The Number of Spanning Trees of thern-Lattice Network

Definition 16 (see [17, 18]).
Thern-lattice networks R(r,n) are defined as
(21)R(r,n)={Krforn=1R(r,n-1)×Krforn≥2,
where Kr is a complete graph of r points.
Whenr=2, R(2,n) is well known, the Boolean n-cube network.
We denoteR(r,n)=Kr(1)×Kr(2)×⋯×Kr(n).Lemma 17.
The eigenvalues ofH(Kr) are r with multiplicity r-1 and 0 with multiplicity 1.Proof.
SinceH(Kr)=rIr-Jr, where Jr is the matrix of all ones, letting PKr(λ) be the character polynomial of H(Kr), we obtain by Gaussian elimination
(22)PKr(λ)=λ|111⋯10λ-r-1⋯⋯00λ-r⋯⋯⋮⋮⋮⋱⋯0000λ-r|=λ(λ-r)r-1.
Hence the result follows.Lemma 18.
If the distinct eigenvalues of the Kirchhoff matrixH(R(r,n)) are 0=λ0≤λ1⋯≤λn-1≤λn then(23)λ0=withmultiplicityC(n,n)=1λ1=rwithmultiplicity(r-1)C(n,n-1)λ2=2rwithmultiplicity(r-1)2C(n,n)⋮λn-1=(n-1)rwithmultiplicity(r-1)n-1C(n,1)λn=nrwithmultiplicity(r-1)nC(n,0),
whereC(n,r)=n!/r!(n-r)!.Proof.
SinceR(r,n)=Kr(1)×Kr(2)×⋯×Kr(n)and by Lemma 13, we obtain each of eigenvalues of H(R(r,n))=∑i=1n‍one of eigenvalues of H(Kr(i)).
Hence if we take the eigenvalue 0 ofH(Kr(i)) for i=1,2,…,n then λ0=0 with multiplicity C(n,n)=1. If we take the eigenvalue r of H(Kr(l)) for some one l∈{1,2,…,n} and the eigenvalue 0 of H(Kr(i)) for each i∈{1,2,…,n}-{l} then λ1=r with multiplicity (r-1)C(n,n-1). If we take the eigenvalue r of H(Kr(l)) and H(Kr(m)), respectively, for l,m∈{1,2,…,n} and the eigenvalue 0 of H(Kr(i)) for each i∈{1,2,…,n}-{l,m}, then λ2=2r with multiplicity (r-1)2C(n,n). We keep performing the same process. Hence the result follows.The main theorem in [17, 18] can be obtained much more simply by Theorem 19 as follows.Theorem 19 (see [17]).
The number of spanning trees ofR(r,n) is
(24)t(R(r,n))=rrn-n-1∏i=2niC(n,i)(r-1)i.Proof.
Since the degree ofR(r,n) is n(r-1), the number of points of R(r,n) is rn. By Lemma 18 and Theorem 15, we obtain
(25)t(R(r,n))=1rn·rC(n,n-1)(r-1)·(2r)C(n,n-2)(r-1)2·(3r)C(n,n-3)(r-1)3⋯(nr)C(n,0)(r-1)n=1rn·rC(n,n-1)(r-1)+C(n,n-2)(r-1)2+C(n,n-3)(r-1)3+⋯+C(n,0)(r-1)n·∏i=1niC(n,n-i)(r-1)i=1rn·rrn-1·∏i=1niC(n,n-i)(r-1)i=rrn-n-1∏i=2niC(n,i)(r-1)i.Corollary 20 (see [18]).
The number of spanning trees of the Booleann-cube network Bn is
(26)t(Bn)=22n-n-1∏i=2niC(n,i).Proof.
SinceBn=R(2,n), by Theorem 15, the result follows.


## 6. The Number of Spanning Trees of the2×3⋯×n-Lattice Network

Definition 21.
The2×3⋯×n lattice network Qn can be defined recursively by Q2=K2 and Qn=Kn×Qn-1.
ThusQn has n! points. We denote Qn=K2×K3×⋯×Kn.Theorem 22.
The number of spanning trees ofQn is
(27)t(Qn)=1n!∏i=1n-1∏2≤r1<r2<⋯<ri≤n(∑j=1irj)∏j=1i(rj-1).Proof.
Since the eigenvalues ofH(Kr) are r with multiplicity r-1 and 0 with multiplicity 1, the distinct ∑i=0n-1C(n-1,i)=2n-1 eigenvalues of Qn are 0 and λi,r1,r2,…,ri=∑j=1irj with multiplicity (r1-1)(r2-1)⋯(ri-1), where r1,r2,…,ri, satisfying 2≤r1<r2<⋯<ri≤n,  i=1,2,…,n-1, are nonzero eigenvalues of H(Kr1),H(Kr2),…,H(Kri), respectively, and take zero eigenvalues for the remaining H(Kr), where r≠r1,r2,…,ri,  r=2,3,…,n-1. By Lemma 13 and Theorem 15, the result follows.Example 23.
The number of spanning trees ofQ3 and Q4 is as shown in Figure 1, where t(Q3)=(1/3!)2(2-1)3(3-1)(2+3)(2-1)(3-1)=75 and t(Q4)=(1/4!)2(2-1)3(3-1)4(4-1)(2+3)(2-1)(3-1)(2+4)(2-1)(4-1)(3+4)(3-1)(4-1)(2+3+4)(2-1)(3-1)(4-1) = 1620609272381440.Figure 1


## 7. The Number of Spanning Trees of the Generalized Booleann-Cube Network

Definition 24.
The generalized Booleann-cube network BR(r,n) can be defined by
(28)BR(r,n)={Crforn=1BR(r,n-1)×K2forn≥2,
where Cr is a cycle with r points. One denotes BR(r,n)=Cr×K2×⋯×K2.
SettingEn is the n×n matrix by
(29)En=[0100⋯00010⋯0⋮⋮⋮⋮⋯⋮0000⋯11000⋯0],Eni=1i+1[00⋮00⋯⋯⋮⋯⋯00⋮1000⋮0110⋮0001⋮0000⋮00⋯⋯⋯⋯⋯00⋮00]i.Lemma 25.
The eigenvalues of the adjacent matrixA(Kr) are -1 with multiplicity r-1 and r-1 with multiplicity 1.Lemma 26 (see [33]).
IfB is a sequence matrix, λ is an eigenvalue of B, and f is a polynomial then f(λ) is the eigenvalue of f(B).Lemma 27.
The eigenvalues of the adjacent matrixA(Cn) are 2cos⁡⁡(2πk/n) for k=0,1,2,…,n-1.Proof.
Since(30)det⁡(λIn-En)=|λ-10⋯00λ-100⋮0⋱⋱00⋯0λ-1-10⋯0λ|=λ·λn-1+(-1)(-1)n+1(-1)n-1=λn-1,
the eigenvalues of En are e(2πk/n)i for k=0,1,2,…,n-1. It follows that A(Cn)=En+Enn-1. By Lemma 26, the eigenvalues of A(Cn) are e(2πk/n)i+(e(2πk/n)i)n-1=e(2πk/n)i+(e2πki-(2πk/n)i)=e(2πk/n)i+e-(2πk/n)i=2cos⁡(2πk/n) for k=0,1,2,…,n-1.The main theorem in [13] can be obtained much more simply as follows.Theorem 28 (see [13]).
The number of spanning trees ofBR(r,n) is
(31)t(BR(r,n))=r2r(2n-1-1)-n+1×∏i=1n-1(i∏k=1r-1(i+1-cos⁡2πkr))C(n-1,i).Proof.
It follows that the points ofBR(r,n) are r·2n-1 and the degree of any edge of BR(r,n) is n+1. By Lemma 25, the eigenvalues of the adjacent matrix A(K2) are -1 and 1. By Lemmas 13 and 27, the distinct eigenvalues of the adjacent matrix A(BR(r,n)) are
(32)(n-2i-1)+2cos⁡2πkrk=0,1,…,r-1withmultiplicityC(n-1,i),
where i=0,1,…,n-1.
Whenk=0 and i=0, the eigenvalue is n+1. When k=0 and i=0,1,…,n-1, the eigenvalues are (n-2i-1)+2. By Theorem 14,
(33)t(BR(r,n))=1r·2n-1∏i=1n-1((n+1)-((n-2i-1)+2))C(n-1,i)·∏k=1r-1∏i=0n-1((n+1)-((n-2i-1)+2cos⁡2πkr))C(n-1,i)=1r·2n-1∏i=1n-1(2i)C(n-1,i)·∏k=1r-1∏i=0n-1(2(i+1-cos⁡2πkr))C(n-1,i).
Since ∏i=0n-12C(n-1,i)=2∑i=0n-1C(n-1,i) = 22n-1 and ∏i=1n-12C(n-1,i)=22n-1-1, hence
(34)t(BR(r,n))=1r·2n-122n-1-12(r-1)2n-1∏i=1n-1iC(n-1,i)·∏k=1r-1∏i=0n-1(i+1-cos⁡2πkr)C(n-1,i).
Since ∏k=1r-1sin2(πk/r)=r2 and ∏k=1r-1(1-cos⁡⁡(2πk/r))=∏k=1r-12sin2(πk/r)=r2/2r-1 as i=1,
(35)t(BR(r,n))=r2r(2n-1-1)-n+1∏i=1n-1iC(n-1,i)·∏k=1r-1∏i=1n-1(i+1-cos⁡2πkr)C(n-1,i)=r2r(2n-1-1)-n+1×∏i=1n-1(i∏k=1r-1(i+1-cos⁡2πkr))C(n-1,i).


## 8. The Number of Spanning Trees of the Hypercube Network

Definition 29.
The hypercube networkH(r,m) can be defined by
(36)H(r,m)={Crform=1H(r,m-1)×Crform≥2,
where Cr is a cycle with r points.Theorem 30.
The number of spanning trees ofH(r,m) is
(37)t(H(r,m))=2rm-1rm∏l1,l2,…,lm(m-∑i=1mcos⁡2πlir),
where l1,l2,…,lm satisfy (l1,l2,…,lm)∈{0,1,…,r-1}×{0,1,…,r-1}×⋯×{0,1,…,r-1}-{(0,0,…,0)}.Proof.
It follows that the points ofH(r,m) are rm and the degree of any edge of H(r,m) is 2m. By Lemma 26 and Theorem 14,
(38)t(H(r,m))=1rm∏l1,l2,…,lm(2m-2∑i=1mcos⁡2πlir)=2rm-1rm∏l1,l2,…,lm(m-∑i=1mcos⁡2πlir),
where l1,l2,…,lm satisfy (l1,l2,…,lm)∈{0,1,…,r-1}×{0,1,…,r-1}×⋯×{0,1,…,r-1}-{(0,0,…,0)}.


## 9. Conclusion

Due to the high dependence of the network design and reliability problem, electrical circuits designing issue are on the graph theory. For example, the larger degree of points a network has, the more I/O ports and edges are needed and the more cost is required. The evaluation of this number not only is interesting from a mathematical (computational) perspective but also is an important issue on practical applications. However, the study for spanning trees of the Cartesian product of regular graphs remains an open and important invariant. In this paper, the eigenvalues of the Kirchhoff matrix of Cartesian product of two regular graphs,G1 and G2, are given by λ+γ as λ and γ vary through the eigenvalues of the Kirchhoff matrices H(G1) and H(G2), respectively. By this result, the formula for the number of spanning trees of the four regular networks can be simply obtained. Using this formula, the main results in [13, 17, 18] can be obtained much more simply and will be extended.



---

*Source: 750618-2014-07-14.xml*