# Number of Spanning Trees of Different Products of  Complete and Complete Bipartite Graphs

Authors: S. N. Daoud
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Spanning trees have been found to be structures of paramount importance in both theoretical and practical problems. In this paper we derive new formulas for the complexity, number of spanning trees, of some products of complete and complete bipartite graphs such as Cartesian product, normal product, composition product, tensor product, symmetric product, and strong sum, using linear algebra and matrix theory techniques.


---

## Body

## 1. Introduction

The number of spanning trees of a graph is an important, well-studied quantity in graph theory and appears in a number of applications. The most notable application fields are network reliability [1–4], enumerating certain chemical isomers [5], and counting of the Eulerian circuits in a graph [6]. Every connected graph has a spanning tree. A spanning tree of a graph G is a tree that (i) is a subgraph of G (i.e., that includes only edges from G) and (ii) includes every vertex of G. The most classical interest concerning a spanning tree is the number of spanning trees, also called the complexity of the graph G and denoted by τ(G). Kirchhoff [7] gave a formula for determining it, which is known as the matrix tree theorem. The spanning trees of a graph G are the value of any cofactor of the matrix D(G)-A(G), where D(G) is the degree matrix (the ith diagonal entry is equal to the degree of the ith vertex and the other entry is equal to zero) and A(G) is the adjacency matrix of G (the entry (i,j) is equal to the number of edges between ith vertex and jth vertex), respectively. This topic is still much studied, in particular, in explicit formulas of the number of spanning trees of some special classes. That for complete graphs is most famous among such classes; the number of spanning trees of Kn is nn-2, called Cayley’s formula [8]. Several proofs of Cayley’s formula are known, and the most famous one is due to Prüfer [9]. The explicit formulas of the number of spanning trees are known for other classes than complete graphs: complete bipartite graphs [10–13], regular graphs [14], circulant graphs [15–19], pyramid graphs [20], and so on.Now we introduce the following Lemma which describes a way to calculate the number of spanning trees by an extension of Kirchhoff formula.Lemma 1 (see [21]).
LetG be a graph with n vertices. Then
(1)τ(G)=1n2det⁡⁡(nI-D-+A-),
where A-, D- are the adjacency and degree matrices of G-, the complement of G, respectively, and I is the n×n unit matrix.Lemma 2.
LetAn(x) be n×n matrix, x≥2 such that
(2)An(x)=(x1⋯⋯⋯11x⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱x11⋯⋯⋯1x).
Then
(3)det⁡⁡(An(x))=(x+n-1)(x-1)n-1.Proof.
From the definition of the circulant determinants, we have(4)det⁡⁡(An(x))=det⁡⁡(x1⋯⋯⋯11x⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱x11⋯⋯⋯1x)=∏j=1n(x+ωj+ωj2+ωj3+⋯+ωjn-1)=(x+1+1+⋯+1)×∏j=1,ωj≠1n(x+ωj+ωj2+ωj3+⋯+ωjn-1︸=-1)=(x+n-1)×(x-1)n-1.
We can generalize the above lemma as follows.Lemma 3.
LetA,B∈Fn×n, and F∈Fkn×kn such that
(5)F=(AB⋯⋯⋯BBA⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱ABB⋯⋯⋯BA).
Then
(6)det⁡⁡F=[det⁡⁡(A-B)]k-1det⁡⁡[A+(k-1)B].Lemma 4 (see [22]).
LetA∈Fn×n, B∈Fn×m, C∈Fm×n, and D∈Fm×m. Assume that A and D are nonsingular matrices. Then:
(7)det⁡⁡(ABCD)=(-1)nmdet⁡⁡(A-BD-1C)det⁡⁡D=(-1)nmdet⁡⁡Adet⁡⁡(D-CA-1B).
Formulas in Lemmas 2, 3, and 4 give some sort of symmetry in some matrices which facilitates our calculation of determinants.


## 2. Number of Spanning Trees of Cartesian Product of Graphs

The Cartesian product,G1×G2, of two graphs G1 and G2 is the simple graph with vertex set V(G1×G2)=V1×V2 and edge set E(G1×G2)=[(E1×V2)∪(V1×E2)] such that two vertices (u1,u2) and (v1,v2) are adjacent in G1×G2 if and only if either u1=v1 and u2 is adjacent to v2 in G2 or u1 is adjacent to v1 in G1 and u2=v2 [23].Theorem 5.
Form,n≥1and r≥2, we have
(8)τ(Kr×Km,n)=rr-2mn-1nm-1(m+r)(r-1)(n-1)×(n+r)(r-1)(m-1)(m+n+r)r-1.Proof.
Applying Lemma1, we have
(9)τ(Kr×Km,n)=1(r(m+n))2det⁡⁡(r(m+n)I-D-+A-)=1r2(m+n)2×det⁡⁡(n+r1⋯10⋯⋯001⋯11⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯1⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯1n+r0⋯⋯01⋯101⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0m+r1⋯11⋯⋯101⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯1m+r1⋯⋯11⋯10⋯⋯⋯⋯⋯⋯⋯⋯01⋯11⋯⋯1⋯⋯⋯⋮⋯⋯⋯⋯01⋯11⋯⋯11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯101⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯1⋯101⋯⋯11⋯⋯101⋯1⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯101⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱11⋯⋯11⋯10⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯11⋯10⋯⋯⋯⋯⋯⋯⋯⋯01⋯11⋯⋯1n+r1⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯1⋯101⋯⋯11⋯1n+r0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯101⋯10⋯⋯0m+r1⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱1⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯11⋯100⋯⋯01⋯1m+r).
Using Lemma 3, we get
(10)τ(Kr×Km,n)=1r2(m+n)2det⁡⁡(AB⋯⋯⋯BBA⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱ABB⋯⋯⋯BA)=1(r(m+n))2[det⁡⁡(A-B)]r-1[det⁡⁡(A+(r-1)B)]=1r2(m+n)2×(det⁡⁡(n+r0⋯0-1⋯⋯-10⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯0n+r-1⋯⋯-1-1⋯⋯-1m+r0⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0-1⋯⋯-10⋯0m+r))r-1×det⁡⁡(n+rr⋯r(r-1)⋯⋯(r-1)r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r⋮⋱⋱⋮r⋯rn+r(r-1)⋯⋯(r-1)(r-1)⋯⋯(r-1)m+rr⋯r⋮⋱⋱⋮r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r(r-1)⋯⋯(r-1)r⋯rm+r)=1r2(m+n)2(det⁡⁡(ABBTC))r-1×det⁡⁡(DEETF).
Using Lemma 4, we obtain
(11)τ(Kr×Km,n)=1r2(m+n)2×(det⁡⁡A)r-1(det⁡⁡(C-BTA-1B))r-1×det⁡⁡Ddet⁡⁡(F-ETD-1E)=1r2(m+n)2(det⁡⁡(n+r0⋯00⋱⋱⋮⋮⋱⋱00⋯0n+r)m×m)r-1×(det⁡⁡(n(m+r)+(r-1)m+r2n+r-mn+r⋯-mn+r-mn+r⋱⋱⋮⋮⋱⋱-mn+r-mn+r⋯-mn+rn(m+r)+(r-1)m+r2n+r)n×n)r-1×det⁡⁡(n+rr⋯rr⋱⋱⋮⋮⋱⋱rr⋯rn+r)m×m×det⁡⁡(n(m+r)+rm2+(2r-1)mn+rmrn+(2r-1)mn+rm⋯rn+(2r-1)mn+rmrn+(2r-1)mn+rm⋱⋱⋮⋮⋱⋱rn+(2r-1)mn+rmrn+(2r-1)mn+rm⋯rn+(2r-1)mn+rmn(m+r)+rm2+(2r-1)mn+rm)n×n=1r2(m+n)2(n+r)m(r-1)(-mn+r)n(r-1)×(det⁡⁡(n(m+r)+(r-1)m+r2-m1⋯11⋱⋱⋮⋮⋱⋱11⋯1n(m+r)+(r-1)m+r2-m)n×n)r-1×rmdet⁡⁡(n+rr1⋯11⋱⋱⋮⋮⋱⋱11⋯1n+rr)m×m×(rn+(2r-1)mn+rm)n×det⁡⁡(n(m+r)+rm2+(2r-1)mrn+(2r-1)m1⋯11⋱⋱⋮⋮⋱⋱11⋯1n(m+r)+rm2+(2r-1)mrn+(2r-1)m)n×n.
Using Lemma 2, we have
(12)τ(Kr×Km,n)=1r2(m+n)2×(n+r)m(r-1)×(-mn+r)n(r-1)[-nm+rn+(r-1)m+r2m+n-1]r-1×[-nm+rn+(r-1)m+r2m-1](r-1)(n-1)×rm(n+rr+m-1)(n+rr-1)m-1×(nr+(2r-1)mn+rm)n×[n(m+r)+rm2+(2r-1)mrn+(2r-1)m+n-1]×[n(m+r)+rm2+(2r-1)mrn+(2r-1)m-1](n-1)=1r2(m+n)2×rr-1(n+r)(m-n)(r-1)×(m+n+r)r-1×(rm+rn+mn+r2)(r-1)(n-1)×(n+rm)×nm-1×1(n+rm)n×r(m+n)2×(n+rm)n-1×mn-1=rr-2×(n+r)(m-n)(r-1)×mn-1×nm-1×(m+n+r)r-1×(rm+rn+mn+r2)(r-1)(n-1)=rr-2×mn-1×nm-1×(m+r)(r-1)(n-1)×(n+r)(r-1)(m-1)×(m+n+r)r-1.
Specially,
(13)τ(Kr×Kn,n)=rr-2×n2n-2×(2n+r)r-1×(n+r)2(r-1)(n-1);n≥1.


## 3. Number of Spanning Trees of Normal Product of Graphs

The normal product, or the strong product,G1∘G2, of two graphs G1 and G2 is the simple graph with V(G1∘G2)=V1×V2, where (u1,u2) and (v1,v2) are adjacent in G1∘G2 if and only if either u1=v1 and u2 is adjacent to v2, or u1 is adjacent to v1 and u2=v2, or u1 is adjacent to v1 and u2 is adjacent to v2, [24].Theorem 6.
Form,n≥1 and r≥2, we have
(14)τ(Kr∘Km,n)=rrm+rn-2mn-1nm-1×(m+1)n(r-1)(n+1)m(r-1).Proof.
Applying Lemma1, we have
(15)τ(Kr∘Km,n)=1(r(m+n))2det⁡⁡(r(m+n)I-D-+A-)=1r2(m+n)2×det⁡⁡(r(n+1)1⋯10⋯⋯001⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯1r(n+1)0⋯⋯01⋯100⋯⋯0r(m+1)1⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯1r(m+1)0⋯⋯001⋯10⋯⋯0⋯⋯⋯⋯1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯100⋯⋯0⋯⋯⋯⋯0⋯⋯001⋯1⋯⋯⋯⋯⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯10⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯01⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋯⋯⋯⋯⋯⋯⋯⋯1⋯10⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0hhhhhhhhhhhhh0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯01⋯1⋯⋯⋯⋯⋯⋯⋯⋯1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯10⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯01⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋯⋯⋯⋯1⋯100⋯⋯0⋯⋯⋯⋯0⋯⋯001⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋯⋯⋯⋯0⋯⋯01⋯100⋯⋯0r(n+1)1⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯1r(n+1)0⋯⋯001⋯10⋯⋯0r(m+1)1⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯100⋯⋯01⋯1r(m+1)).
Using Lemma 3, we get
(16)τ(Kr∘Km,n)=1r2(m+n)2×det⁡⁡(AB⋯⋯⋯BBA⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱ABB⋯⋯⋯BA)=1(r(m+n))2[det⁡⁡(A-B)]r-1[det⁡⁡(A+(r-1)B)]=1r2(m+n)2(det⁡⁡(r(n+1)0⋯00⋯⋯00⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯0r(n+1)0⋯⋯00⋯⋯0r(m+1)0⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱00⋯⋯00⋯0r(m+1)))r-1×det⁡⁡(r(n+1)r⋯r0⋯⋯0r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r⋮⋱⋱⋮r⋯rr(n+1)0⋯⋯00⋯⋯0r(m+1)r⋯r⋮⋱⋱⋮r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r0⋯⋯0r⋯rr(m+1))=1r2(m+n)2(det⁡⁡(r(n+1)0⋯00⋱⋱⋮⋮⋱⋱00⋯0r(n+1))m×m)r-1×(det⁡⁡(r(m+1)0⋯00⋱⋱⋮⋮⋱⋱00⋯0r(m+1))n×n)r-1×det⁡⁡(r(n+1)r⋯rr⋱⋱⋮⋮⋱⋱rr⋯rr(n+1))m×m×det⁡⁡(r(m+1)r⋯rr⋱⋱⋮⋮⋱⋱rr⋯rr(m+1))n×n.
Using Lemma 2, we obtain
(17)τ(Kr∘Km,n)=1r2(m+n)2(r(n+1))m(r-1)(r(m+1))n(r-1)×(rm×(n+m)×nm-1)(rn×(n+m)×mn-1)=rr(m+n)-2mn-1nm-1(m+1)n(r-1)(n+1)m(r-1).
Specially,
(18)τ(Kr∘Kn,n)=r2(rn-1)×n2(n-1)×(n+1)2n(r-1);n≥1.


## 4. Number of Spanning Trees of Composition Product of Graphs

The composition, or lexicographic product,G1[G2], of two graphs G1 and G2 is the simple graph with V1×V2 as the vertex set in which the vertices (u1,u2) and (v1,v2) are adjacent if either u1 is adjacent to v1 or u1=v1 and u2 is adjacent to v2 in G2 [24].Theorem 7.
Form,n≥1 and r≥2, we get
(19)τ(Kr[Km,n])=r2(r-1)(m+n)2(r-1)(rm+rn-m)r(m-1)×(rm+rn-n)r(n-1).Proof.
Applying Lemma1, we have
(20)τ(Kr[Km,n])=1r2(m+n)2×(det⁡⁡(rn+(r-1)m+11⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1rn+(r-1)m+10⋯⋯00⋯⋯0rm+(r-1)n+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯1rm+(r-1)n+1))r=1r2(m+n)2(det⁡⁡(rn+(r-1)m+11⋯11⋱⋱⋮⋮⋱⋱11⋯1rn+(r-1)m+1)m×m)r×(det⁡⁡(rm+(r-1)n+11⋯11⋱⋱⋮⋮⋱⋱11⋯1rm+(r-1)n+1)n×n)r.
Using Lemma 2, we obtain
(21)τ(Kr[Km,n])=r2(r-1)(m+n)2(r-1)×(rm+rn-m)r(m-1)(rm+rn-n)r(n-1).
Specially,
(22)τ(Kr[Kn,n])=(2r)2(r-1)n2(rn-1)(2r-1)2r(n-1);n≥1.


## 5. Complexity of Tensor Product of Graphs

The tensor product, or Kronecker product,G1⊗G2, of two graphs G1 and G2 is the simple graph with V(G1⊗G2)=V1×V2, where (u1,u2) and (v1,v2) are adjacent in G1⊗G2 if and only if u1 is adjacent to v1 in G1 and u2 is adjacent to v2 in G2 [24].Theorem 8.
Form,n≥1 and r≥2, we have
(23)τ(Kr⊗Km,n)=rr-2(r-2)r-1(r-1)r(m+n-2)+1mrn-1nrm-1.Proof.
Applying Lemma1, we get
(24)τ(Kr⊗Km,n)=1(r(m+n))2det⁡⁡(r(m+n)I-D-+A-)=1r2(m+n)2×det⁡⁡((r-1)n+11⋯11⋯⋯11⋯⋯11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯1(r-1)n+11⋯⋯11⋯⋯11⋯⋯1(r-1)m+11⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯11⋯1(r-1)m+10⋯⋯01⋯⋯10⋯⋯0⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯0⋯⋯⋯⋯0⋯⋯01⋯⋯1⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0hhhhhhhhh0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯1⋯⋯10⋯⋯0⋯⋯⋯⋯0⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯0⋯⋯01⋯⋯10⋯⋯0(r-1)n+11⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯1(r-1)n+11⋯⋯11⋯⋯11⋯⋯1(r-1)m+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱11⋯⋯11⋯⋯11⋯1(r-1)m+1).
Using Lemma 3, we obtain
(25)τ(Kr⊗Km,n)=1r2(m+n)2det⁡⁡(AB⋯⋯⋯BBA⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱ABB⋯⋯⋯BA)=1(r(m+n))2[det⁡⁡(A-B)]r-1[det⁡⁡(A+(r-1)B)]=1r2(m+n)2×(det⁡⁡((r-1)n0⋯01⋯⋯10⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯0(r-1)n1⋯⋯11⋯⋯1(r-1)m0⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱01⋯⋯10⋯0(r-1)m))r-1×det⁡⁡((r-1)n+rr⋯r1⋯⋯1r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r⋮⋱⋱⋮r⋯r(r-1)n+r1⋯⋯11⋯⋯1(r-1)m+rr⋯r⋮⋱⋱⋮r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r1⋯⋯1r⋯r(r-1)m+r)=1r2(m+n)2(det⁡⁡(ABBTC))r-1×det⁡⁡(DEETF).
Using Lemma 4, we obtain
(26)τ(Kr⊗Km,n)=1r2(m+n)2×(det⁡⁡A)r-1(det⁡⁡(C-BTA-1B))r-1×det⁡⁡Ddet⁡⁡(F-ETD-1E)=1r2(m+n)2(det⁡⁡((r-1)n0⋯00⋱⋱⋮⋮⋱⋱00⋯0(r-1)n)m×m)r-1×det⁡⁡([(r-1)2m+(r2-r)]n+(r2-r)m2+(r2-1)mrm+(r-1)n(r2-1)m+(r2-r)nrm+(r-1)n(r2-1)m+(r2-r)nrm+(r-1)n⋱⋮⋱(r2-1)m+(r2-r)nrm+(r-1)n⋯hhhhhhhhhh⋯(r2-1)m+(r2-r)nrm+(r-1)n⋱⋮⋱(r2-1)m+(r2-r)nrm+(r-1)n(r2-1)m+(r2-r)nrm+(r-1)n[(r-1)2m+(r2-r)]n+(r2-r)m2+(r2-1)mrm+(r-1)n)n×n×(det⁡⁡(m[(r-1)2n-1](r-1)n-m(r-1)n⋯-m(r-1)n-m(r-1)n⋱⋱⋮⋮⋱⋱-m(r-1)n-m(r-1)n⋯-m(r-1)nm[(r-1)2n-1](r-1)n)n×n)r-1×det⁡⁡((r-1)n+rr⋯rr⋱⋱⋮⋮⋱⋱rr⋯r(r-1)n+r)m×m=1r2(m+n)2((r-1)n)m(r-1)×(-m(r-1)n)n(r-1)(det⁡⁡(-[(r-1)2n-1]1⋯11⋱⋱⋮⋮⋱⋱11⋯1-[(r-1)2n-1])n×n)r-1×rmdet⁡⁡((r-1)n+rr1⋯11⋱⋱⋮⋮⋱⋱11⋯1(r-1)n+rr)m×m×((r2-1)m+(r2-r)nrm+(r-1)n)n×det⁡⁡([(r-1)2m+(r2-r)]n+(r2-r)m2+(r2-1)m(r2-1)m+(r2-r)n1⋯11⋱⋱⋮⋮⋱⋱11⋯1[(r-1)2m+(r2-r)]n+(r2-r)m2+(r2-1)m(r2-1)m+(r2-r)n)n×n.
Using Lemma 2 yields
(27)τ(Kr⊗Km,n)=1r2(m+n)2×(r-1)(r-1)(m-n)×n(r-1)(m-n)×mn(r-1)×[rn(r-2)]r-1×[n(r-1)2](r-1)(n-1)×[rm+(r-1)n]×[(r-1)n]m-1×1(rm+(r-1)n)n×[r(r-1)(m+n)2]×[m(r-1)(rm+(r-1)n)]n-1=rr-2×(r-1)r(m+n)-2r+1×(r-2)r-1×mnr-1×nmr-1.
Specially,
(28)τ(Kr⊗Kn,n)=rr-2×(r-2)r-1×(r-1)2r(n-1)+1×n2(nr-1);n≥1.


## 6. Number of Spanning Trees of Symmetric Product of Graphs

The symmetric product,G1⊕G2, of two graphs G1 and G2 is the simple graph with V(G1⊕G2)=V1×V2, where (u1,u2) and (v1,v2) are adjacent in G1⊕G2 if and only if either u1 is adjacent to v1 in G1 and u2 is not adjacent to v2 in G2 or u1 is not adjacent to v1 in G1 and u2 is adjacent to v2 in G2 [24].Theorem 9.
Form,n≥1 and r≥2, we have
(29)τ(Kr⊕Km,n)=rr-2×((r-1)m+n)r(m-1)×((r-1)n+m)r(n-1)×(m2+n2+rmn)r-1.Proof.
Applying Lemma1, we have
(30)τ(Kr⊕Km,n)=1(r(m+n))2det⁡⁡(r(m+n)I-D-+A-)=1r2(m+n)2×det⁡⁡((r-1)m+n+11⋯10⋯⋯00⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯1(r-1)m+n+10⋯⋯00⋯⋯00⋯⋯0(r-1)n+m+11⋯11⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯1(r-1)n+m+11⋯⋯10⋯⋯01⋯⋯1⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯1⋯⋯⋯⋯1⋯⋯10⋯⋯0⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯1hhhhhhhhhh1⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋯0⋯⋯01⋯⋯1⋯⋯⋯⋯1⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋯⋮⋱⋱⋮⋮⋱⋱⋮⋯⋯⋯⋮1⋯⋯10⋯⋯01⋯⋯1(r-1)m+n+11⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯⋯11⋯1(r-1)m+n+10⋯⋯00⋯⋯00⋯⋯0(r-1)n+m+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯00⋯⋯01⋯1(r-1)n+m+1).
Using Lemma 3, we obtain
(31)τ(Kr⊕Km,n)=1r2(m+n)2det⁡⁡(AB⋯⋯⋯BBA⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱ABB⋯⋯⋯BA)=1(r(m+n))2[det⁡⁡(A-B)]r-1[det⁡⁡(A+(r-1)B)]=1r2(m+n)2×(det⁡⁡((r-1)m+n+11⋯1-1⋯⋯-11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1(r-1)m+n+1-1⋯⋯-1-1⋯⋯-1(r-1)n+m+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1-1⋯⋯-11⋯1(r-1)n+m+1))r-1×det⁡⁡((r-1)m+n+11⋯1(r-1)⋯⋯(r-1)1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1(r-1)m+n+1(r-1)⋯⋯(r-1)(r-1)⋯⋯(r-1)(r-1)n+m+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1(r-1)⋯⋯(r-1)1⋯1(r-1)n+m+1)=1r2(m+n)2(det⁡⁡(ABBTC))r-1×det⁡⁡(DEETF).
Using Lemma 4, we get
(32)τ(Kr⊕Km,n)=1r2(m+n)2×(det⁡⁡A)r-1(det⁡⁡(C-BTA-1B))r-1×det⁡⁡Ddet⁡⁡(F-ETD-1E)=(rm+n)r-1((r-1)m+n)(r-1)(m-1)r2(n+m)2×(det⁡⁡((r-1)n2+[(r2-r+1)m+1]n+rm2+(r-1)mn+rmn+(r-1)mn+rmn+(r-1)mn+rm⋱⋮⋱n+(r-1)mn+rm⋯hhhhhhhhhhhhhhhh⋯n+(r-1)mn+rm⋱⋮⋱n+(r-1)mn+rmn+(r-1)mn+rm(r-1)n2+[(r2-r+1)m+1]n+rm2+(r-1)mn+rm)n×n)r-1×(rm+n)((r-1)m+n)m-1×det⁡⁡((r-1)n2+[(r2-r+1)m+1]n+rm2+(-r2+3r-1)mn+rmn+(-r2+3r-1)mn+rmn+(-r2+3r-1)mn+rm⋱⋮⋱n+(-r2+3r-1)mn+rm⋯hhhhhhhhhhh⋯n+(-r2+3r-1)mn+rm⋱⋮⋱n+(-r2+3r-1)mn+rmn+(-r2+3r-1)mn+rm(r-1)n2+[(r2-r+1)m+1]n+rm2+(-r2+3r-1)mn+rm)n×n=(rm+n)r-1((r-1)m+n)(r-1)(m-1)r2(n+m)2×(n+(r-1)mn+rm)n(r-1)×(det⁡⁡((r-1)n2+[(r2-r+1)m+1]n+rm2+(r-1)mn+(r-1)m1⋯11⋱⋱⋮⋮⋱⋱11⋯1(r-1)n2+[(r2-r+1)m+1]n+rm2+(r-1)mn+(r-1)m)n×n)r-1×(rm+n)((r-1)m+n)m-1×(n+(-r2+3r-1)mn+rm)n×det⁡⁡((r-1)n2+[(r2-r+1)m+1]n+rm2+(-r2+3r-1)mn+(-r2+3r-1)m1⋯11⋱⋱⋮⋮⋱⋱11⋯1(r-1)n2+[(r2-r+1)m+1]n+rm2+(-r2+3r-1)mn+(-r2+3r-1)m)n×n.
Using Lemma 2, we have
(33)τ(Kr⊕Km,n)=1r2(m+n)2×(rm+n)r-1×((r-1)m+n)(r-1)(m-1)×(n+(r-1)mn+rm)(r-1)n×1(n+(r-1)m)(r-1)n×(rn2+rm2+r2nm)r-1×(rm2+(r2-r+1)nm+(r-1)n2)(r-1)(n-1)×(rm+n)×((r-1)m+n)m-1×(n+(-r2+3r-1)mn+rm)n×1(n+(-r2+3r-1)m)n×(rn2+rm2+2rmn)×(rm2+(r2-r+1)nm+(r-1)n2)n-1=rr-2×((r-1)m+n)r(m-1)×((r-1)n+m)r(n-1)×(m2+n2+rmn)r-1.
Specially,
(34)τ(Kr⊕Kn,n)=r2rn-r-2×n2rn-2×(r+2)r-1;n≥1.


## 7. Number of Spanning Trees of Strong Sum of Graphs

The strong sum,G1*G2, of two graphs G1 and G2 is the simple graph with V(G1*G2)=V1×V2 where (u1,u2) and (v1,v2) are adjacent in G1*G2 if and only if u2 is adjacent to v2 in G2 and either u1 is adjacent to v1 in G1 or u1=v1 [24].Theorem 10.
Form,n≥1 and r≥2, we have
(35)τ(Kr*Km,n)=r(m+n)r-2×mrn-1×nrm-1.Proof.
Applying Lemma1, we have
(36)τ(Kr*Km,n)=1(r(m+n))2det⁡⁡(r(m+n)I-D-+A-)=1r2(m+n)2×det⁡⁡(rn+11⋯10⋯⋯01⋯⋯10⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯1rn+10⋯⋯01⋯⋯10⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯0rm+11⋯10⋯⋯01⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯1rm+10⋯⋯01⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯10⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯10⋯⋯00⋯⋯01⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋯⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋮0⋯⋯01⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯10⋯⋯0rn+11⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋯⋯⋯⋯⋯⋯⋯⋯1⋯⋯10⋯⋯01⋯1rn+10⋯⋯0⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯01⋯⋯10⋯⋯0rm+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋯⋯⋯⋯⋯⋯⋯⋯0⋯⋯01⋯⋯10⋯⋯01⋯1rm+1).
Using Lemma 3, we obtain
(37)τ(Kr*Km,n)=1r2(m+n)2det⁡⁡(AB⋯⋯⋯BBA⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱ABB⋯⋯⋯BA)=1(r(m+n))2[det⁡⁡(A-B)]r-1[det⁡⁡(A+(r-1)B)]=1r2(m+n)2(det⁡⁡(rn0⋯00⋯⋯00⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯0rn0⋯⋯00⋯⋯0rm0⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱00⋯⋯00⋯0rm))r-1×det⁡⁡(r(n+1)r⋯r0⋯⋯0r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r⋮⋱⋱⋮r⋯rr(n+1)0⋯⋯00⋯⋯0r(m+1)r⋯r⋮⋱⋱⋮r⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱r0⋯⋯0r⋯rr(m+1))=1r2(m+n)2[(rn)m(rm)n]r-1×rmdet⁡⁡(n+11⋯11⋱⋱⋮⋮⋱⋱11⋯1n+1)m×m×rndet⁡⁡(m+11⋯11⋱⋱⋮⋮⋱⋱11⋯1m+1)n×n.
Using Lemma 2, we get
(38)τ(Kr*Km,n)=1r2(m+n)2×r(m+n)(r-1)×nm(r-1)×mn(r-1)×r(m+n)×(n+1+m-1)(n+1-1)m-1×(m+1+n-1)(m+1-1)n-1=r(m+n)r-2×mnr-1×nmr-1.
Specially,
(39)τ(Kr*Kn,n)=(nr)2(rn-1);n≥1.


## 8. Conclusion

Driving formulas for different types of graphs can prove to be helpful in identifying those graphs that contain the maximum number of spanning trees. Such an investigation has practical consequence related to network reliability. Some computationally hard problems, such as the Steiner tree problem and the traveling salesperson problem, can be solved approximately by using spanning trees [25]. Due to the high dependence of the network design and reliability on the graph theory we introduced the above important theorems and lemmas and their proofs.



---

*Source: 965105-2014-07-02.xml*