# Complexity of Products of Some Complete and Complete Bipartite Graphs

Authors: S. N. Daoud
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The number of spanning trees in graphs (networks) is an important invariant; it is also an important measure of reliability of a network. In this paper, we derive simple formulas of the complexity, number of spanning trees, of products of some complete and complete bipartite graphs such as cartesian product, normal product, composition product, tensor product, and symmetric product, using linear algebra and matrix analysis techniques.


---

## Body

## 1. Introduction

In this work we deal with simple and finite undirected graphsG=(V,E), whereVis the vertex set andEis the edge set. For a graphG, a spanning tree inGis a tree which has the same vertex set asG. The number of spanning trees inG, also called the complexity of the graph, denoted byτ(G), is a well-studied quantity (for long time). A classical result of Kirchhoff [1], can be used to determine the number of spanning trees forG=(V,E). LetV={v1,v2,…,vn}; then the Kirchhoff matrixHdefined asn×n, characteristic matrix,H=D-A, whereDis the diagonal matrix whose elements are the degrees of the vertices ofG. WhileAis the adjacency matrix ofG,H=[aij]is defined as follows:(i)
aij=-1viandvjare adjacent andi≠j,(ii)
aijequals the degree of vertexviifi=j,(iii)
aij=0otherwise. All of the cofactors ofHare equal toτ(G). There are other methods for calculatingτ(G). Letμ1≥μ1≥⋯≥μpdenote the eigenvalues ofHmatrix of appoint graph. Then it is easily shown thatμp=0. Furthermore, Kelmans and Chelnokov [2] have shown thatτ(G)=(1/p)∏k=1p-1μk. The formula for the number of spanning trees in a d-regular graphGcan be expressed asτ(G)=(1/p)∏k=1p-1(d-λk),whereλ0=d,λ1,λ2,…,λp-1are the eigenvalues of the corresponding adjacency matrix of the graph. However, for a few special families of graphs there exist simple formulas that make it much easier to calculate and determine the number of corresponding spanning trees especially when these numbers are very large. One of the first results is due to Cayley [3] who showed that the complete graph onnvertices,Knhasnn-2spanning trees,n≥2. Another result is thatτ(Kp,q)=pq-1qp-1,p,q≥1, whereKp,qis the complete bipartite graph with bipartite sets containingpandqvertices, respectively. It is well known, as in, for example, [4, 5]. Another result is due to Sedla´cˇek [6] who derived a formula for the wheel onn+1vertices,Wn+1; he showed thatτ(Wn+1)=((3+5)/2)n+((3-5)/2)n-2, forn≥3. Sedlacek [7] also later derived a formula for the number of spanning trees in a Mobius ladder,Mn,τ(Mn)=(n/2)[(2+3)n+(2-3)n+2]forn≥2. Another class of graphs by Boesch et al., for which an explicit formula has been derived, is based on a prism [8, 9].Now, we can introduce the following lemmas.Lemma 1 (see [10]).
Considerτ(G)=(1/n2)det(nI-D-+A-)whereA-andD-are the adjacency and degree matrices ofG-and the complement ofG, respectively, andIis then×nunit matrix.Lemma 2.
LetEn(x)ben×nmatrix,x≥2such that
(1)En(x)=(x1⋯⋯⋯11⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱11⋯⋯⋯1x).
Then,
(2)det(En)=(x+n-1)(x-1)n-1.Proof.
From the definition of the circulant determinants, we have(3)det(En(x))=det(x1⋯⋯⋯11⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱11⋯⋯⋯1x)=∏j=1n(x+ωj+ωj2+ωj3+⋯+ωjn-1)=(x+1+1+⋯+1)m×∏j=1,ωj≠1n(x+ωj+ωj2+ωj3+⋯+ωjn-1︸=-1)=(x+n-1)×(x-1)n-1.We can generalize the previous lemma as follows.Lemma 3.
LetA,B∈Fn×nandF∈Fkn×knsuch that
(4)F=(AB⋯⋯⋯BB⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱⋮⋮⋱⋱⋱⋱BB⋯⋯⋯BA).
Then,
(5)detF=[det(A-B)]k-1det[A+(k-1)B].Lemma 4 (see [11]).
LetA∈Fn×n, letB∈Fn×m, letC∈Fm×n,and letD∈Fm×m;assume thatA,Dare nonsingular matrices. Then
(6)det(ABCD)=(-1)nmdet(A-BD-1C)detD=(-1)nmdetAdet(D-CA-1B).Formulas in Lemmas2, 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, is the simple graph with vertex setV(G1×G2)=V1×V2and edge setE(G1×G2)=[(E1×V2)∪(V1×E2)]such that two vertices(u1,u2)and(v1,v2)are adjacent inG1×G2if and only if eitheru1=v1andu2is adjacent tov2inG2oru1is adjacent tov1inG1andu2=v2[12].Theorem 5.
Forn,m≥1,we have
(7)τ(K2×Km,n)=mn-1nm-1(m+2)n-1×(n+2)m-1(n+m+2).Proof.
Applying Lemma1, we have(8)τ(K2×Km,n)=1(2(m+n))2det(2(m+n)I-D-+A-)=14(m+n)2×det(n+21⋯10⋯⋯001⋯⋯⋯⋯⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋮1⋯1n+20⋯⋯0⋮⋱⋱⋱⋱⋱⋱⋮0⋯⋯0m+21⋯1⋮⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋱⋱⋱⋱10⋯⋯01⋯1m+21⋯⋯⋯⋯⋯1001⋯⋯⋯⋯⋯1n+21⋯10⋯⋯01⋱⋱⋱⋱⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱⋮1⋯1n+20⋯⋯0⋮⋱⋱⋱⋱⋱⋱⋮0⋱⋱0m+21⋯1⋮⋱⋱⋱⋱⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋱⋱⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯⋯⋯⋯⋯100⋯⋯01⋯1m+2)=14(m+n)2det(n+22⋯21⋯⋯12⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱2⋮⋱⋱⋮2⋯2n+21⋯⋯11⋯⋯1m+22⋯2⋮⋱⋱⋮2⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱21⋯⋯12⋯2m+2)×det(n+20⋯0-1⋯⋯-10⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯0n+2-1⋯⋯-1-1⋯⋯-1m+20⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0-1⋯⋯-10⋯0m+2)=14(m+n)2det(ABBTC)×det(DEETF)=14(m+n)2×detAdet(C-BTA-1B)×detDdet(F-ETD-1E)=14(m+n)2det(n+22⋯22⋱⋱⋮⋮⋱⋱22⋯2n+2)m×m×det(n(m+2)+m(2m+3)n+2m2n+3mn+2m⋯2n+3mn+2m2n+3mn+2m⋱⋱⋮⋮⋱⋱2n+3mn+2m2n+3mn+2m⋯2n+3mn+2mn(m+2)+m(2m+3)n+2m)n×n×det(n+20⋯00⋱⋱⋮⋮⋱⋱00⋯0n+2)m×m×det(n(m+2)+(m+4)n+2-mn+2⋯-mn+2-mn+2⋱⋱⋮⋮⋱⋱-mn+2-mn+2⋯-mn+2n(m+2)+(m+4)n+2)n×n=14(m+n)2×2mdet(n+221⋯11⋱⋱⋮⋮⋱⋱11⋯1n+22)m×m×(2n+3mn+2m)ndet(n(m+2)+m(2m+3)2n+3m1⋯11⋱⋱⋮⋮⋱⋱11⋯1n(m+2)+m(2m+3)2n+3m)n×n×det(n+20⋯00⋱⋱⋮⋮⋱⋱00⋯0n+2)m×m×(-mn+2)ndet(n(m+2)+(m+4)-m1⋯11⋱⋱⋮⋮⋱⋱11⋯1n(m+2)+(m+4)-m)n×n=14(m+n)2×2m×(n+22+m-1)(n+22-1)m-1×(2n+3mn+2m)n×(n(m+2)+m(2m+3)2n+3m+n-1)×(n(m+2)+m(2m+3)2n+3m-1)n-1×(n+2)m×(-mn+2)n×(-n(m+2)+(m+4)m+n-1)×(-n(m+2)+(m+4)m-1)n-1.
Thus,(9)τ(K2×Km,n)=mn-1nm-1(m+2)m-1(n+2)m-1×(n+m+2).
In particular,
(10)τ(K2×Kn,n)=2n2n-2(n+1)(n+2)2n-2;n≥1.Theorem 6.
Form,n≥1, we have
(11)τ(K3×Km,n)=3nm-1mn-1(m+3)2n-2(n+3)2m-2×(n+m+3)2.Proof.
Applying Lemma1, we have(12)τ(K3×Km,n)=19(m+n)2det(3(m+n)I-D-+A-)=19(m+n)2×det(n+31⋯10⋯⋯001⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯1n+30⋯⋯01⋯100⋯⋯0m+31⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯1m+31⋯⋯101⋯11⋯⋯1n+31⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯101⋯⋯11⋯1n+31⋯⋯101⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯⋯11⋯100⋯⋯001⋯11⋯⋯101⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯101⋯⋯11⋯101⋯⋯101⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯⋯11⋯101⋯⋯11⋯⋯101⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯11⋯101⋯⋯101⋯11⋯⋯101⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯101⋯⋯11⋯100⋯⋯001⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯101⋯⋯1m+31⋯11⋯⋯101⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯1m+31⋯⋯11⋯101⋯⋯1n+31⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯⋯11⋯1n+30⋯⋯001⋯10⋯⋯0m+31⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯100⋯⋯01⋯1m+3)=19(m+n)2det(ABBBABBBA)=19(m+n)2[det(A-B)]2[det(A+2B)]=19(m+n)2(det(n+30⋯0-1⋯⋯-10⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯0n+3-1⋯⋯-1-1⋯⋯-1m+30⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0-1⋯⋯-10⋯0m+3))2×det(n+33⋯32⋯⋯23⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱3⋮⋱⋱⋮3⋯3n+32⋯⋯22⋯⋯2m+33⋯3⋮⋱⋱⋮3⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱32⋯⋯23⋯3m+3)=19(m+n)2(det(ABBTC))2×det(DEETF)=19(m+n)2×(detA)2(det(C-BTA-1B))2×detDdet(F-ETD-1E).Thus,(13)τ(K3×Km,n)=19(m+n)2(det(n+30⋯00⋱⋱⋮⋮⋱⋱00⋯0n+3)m×m)2×(det(nm+3n+2m+9n+3-mn+3⋯-mn+3-mn+3⋱⋱⋮⋮⋱⋱-mn+3-mn+3⋯-mn+3nm+3n+2m+9n+3)n×n)2×det(n+33⋯33⋱⋱⋮⋮⋱⋱33⋯3n+3)m×m×det(nm+3n+3m2+5mn+3m3n+5mn+3m⋯3n+5mn+3m3n+5mn+3m⋱⋱⋮⋮⋱⋱3n+5mn+3m3n+5mn+3m⋯3n+5mn+3mnm+3n+3m2+5mn+3m)n×n=19(m+n)2(m+3)2m×(-mn+3)2n×(det(mn+3n+2m+9-m1…11⋱⋱⋮⋮⋱⋱11…1mn+3n+2m+9-m))2×3m×det(n+331…11⋱⋱⋮⋮⋱⋱11…1n+33)m×m×(3n+5mn+3m)n×det(mn+3n+2m2+5m3n+5m1…11⋱⋱⋮⋮⋱⋱11…1mn+3n+2m2+5m3n+5m).
Using Lemma2, we have
(14)τ(K3×Km,n)=19(m+n)2×(n+3)2m×(-mn+3)2nm×[-nm+3n+2m+9m+n-1]2m×[-nm+3n+2m+9m-1]2n-2×3m(n+33+m-1)×(n+33-1)m-1×(3n+5mn+3m)nm×[nm+3n+3m2+5m3n+5m+n-1]m×[nm+3n+3m2+5m3n+5m-1]n-1=19(m+n)2(n+3)2mm×[1(n+3)2n×(3n+3m+9)2mm×(nm+3n+3m+9)2n-21(n+3)2n]m×[(n+3m)×nm-1×1(n+3m)nmmm×(6nm+3n2+3m2)mmm×(nm+3m2)n-11(n+3m)n]=3nm-1mn-1(m+3)2n-2(n+3)2m-2(n+m+3)2.
In particular,
(15)τ(K3×Kn,n)=3n2n-2(2n+3)2(n+3)4n-4;n≥1.


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

The normal product, or the strong product,G1∘G2, is the simple graph withV(G1∘G2)=V1×V2,where(u1,u2)and(v1,v2)are adjacent inG1∘G2if and only if eitheru1=v1andu2is adjacent tov2,u1is adjacent tov1andu2=v2, oru1is adjacent tov1andu2is adjacent tov2[13].Theorem 7.
Forn,m≥1,we have
(16)τ(K2∘Km,n)=22m+2n-2×nm-1×mn-1×(n+1)m×(m+1)n.Proof.
Applying Lemma1, we have(17)τ(K2∘Km,n)=14(m+n)2det(2(m+n)I-D-+A-)=14(m+n)2×det(2n+21⋯10⋯⋯001⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯12n+20⋯⋯01⋯100⋯⋯00⋯⋯02m+21⋯10⋯⋯001⋯1⋮⋱⋱11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯12m+20⋯⋯01⋯1001⋯10⋯⋯02n+21⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯100⋯⋯01⋯12n+20⋯⋯00⋯⋯001⋯10⋯⋯02m+21⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯100⋯⋯01⋯12m+2)=14(m+n)2det(2n+22⋯20⋯⋯02⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱2⋮⋱⋱⋮2⋯22n+20⋯⋯00⋯⋯02m+22⋯2⋮⋱⋱⋮2⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱20⋯⋯02⋯22m+2)m×det(2n+20⋯00⋯⋯00⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯02n+20⋯⋯00⋯⋯02m+20⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱00⋯⋯00⋯02m+2)=14(m+n)2det(2n+22⋯22⋱⋱⋮⋮⋱⋱22⋯22n+2)m×m×det(2m+22⋯22⋱⋱⋮⋮⋱⋱22⋯22m+2)n×nm×det(2n+20⋯00⋱⋱⋮⋮⋱⋱00⋯02n+2)m×m×det(2m+20⋯00⋱⋱⋮⋮⋱⋱00⋯02m+2)n×n=14(m+n)2×2m(n+m)nm-1×2n(n+m)mn-1×2m(n+1)m×2n(m+1)n=22m+2n-2×nm-1×mn-1×(n+1)m×(m+1)n.
In particular,(18)τ(K2∘Kn,n)=24n-2×n2n-2×(n+1)2n;n≥1.Theorem 8.
Form,n≥1, we have
(19)τ(K3∘Km,n)=33m+3n-2×nm-1×mn-1×(n+1)2m×(m+1)2n.Proof.
Applying Lemma1, we have(20)τ(K3∘Km,n)=19(m+n)2det(3(m+n)I-D-+A-)=19(m+n)2×det(3n+31⋯10⋯⋯001⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯13n+30⋯⋯01⋯100⋯⋯03m+31⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯13m+30⋯⋯001⋯10⋯⋯03n+31⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯100⋯⋯01⋯13n+30⋯⋯001⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯100⋯⋯001⋯10⋯⋯001⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯100⋯⋯01⋯100⋯⋯001⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯100⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯100⋯⋯001⋯10⋯⋯001⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯100⋯⋯01⋯100⋯⋯001⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯100⋯⋯03m+31⋯10⋯⋯001⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯13m+30⋯⋯01⋯100⋯⋯03n+31⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯13n+30⋯⋯001⋯10⋯⋯03m+31⋯11⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱11⋯100⋯⋯01⋯13m+3)=19(m+n)2det(ABBBABBBA)=19(m+n)2[det(A-B)]2[det(A+2B)]=19(m+n)2(det(3n+30⋯00⋯⋯00⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯03n+30⋯⋯00⋯⋯03m+30⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱00⋯⋯00⋯03m+3))2m×det(3n+33⋯30⋯⋯03⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱3⋮⋱⋱⋮3⋯33n+30⋯⋯00⋯⋯03m+33⋯3⋮⋱⋱⋮3⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱30⋯⋯03⋯33m+3)=19(m+n)2(det(3n+30⋯00⋱⋱⋮⋮⋱⋱00⋯03n+3)m×m)2m×(det(3m+30⋯00⋱⋱⋮⋮⋱⋱00⋯03m+3)n×n)2m×det(3n+33⋯33⋱⋱⋮⋮⋱⋱33⋯33n+3)m×m×det(3m+33⋯33⋱⋱⋮⋮⋱⋱33⋯33m+3)n×n.
Using Lemma2, we have
(21)τ(K3∘Km,n)=19(m+n)2×(3n+3)2m×(3m+3)2n×(3m×(n+m)×nm-1)×(3n×(n+m)×mn-1)=33m+3n-2×nm-1×mn-1×(n+1)2m×(m+1)2n.
In paricular,
(22)τ(K3∘Kn,n)=36n-2×n2n-2×(n+1)4n;n≥1.


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

The composition, or lexicographic product,G1[G2], is the simple graph withV1×V2as the vertex set in which the vertices(u1,u2)and(v1,v2)are adjacent if eitheru1is adjacent tov1oru1=v1andu2is adjacent tov2inG2[13].Theorem 9.
Forn,m≥1, we have
(23)τ(K2[Km,n])=4(m+n)2×(m+2n)2m-2(n+2m)2n-2.Proof.
Applying Lemma1, we have(24)τ(K2[Km,n])=14(m+n)2det(2(m+n)I-D-+A-)=14(m+n)2×det(m+2n+11⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1m+2n+10⋯⋯00⋯⋯0n+2m+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯1n+2m+10⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯0m+2n+11⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1m+2n+10⋯⋯00⋯⋯0n+2m+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯1n+2m+1)=14(m+n)2(det(m+2n+11⋯11⋱⋱⋮⋮⋱⋱11⋯1m+2n+1)m×m)2m×(det(n+2m+11⋯11⋱⋱⋮⋮⋱⋱11⋯1n+2m+1)n×n)2=14(m+n)2(2n+2m)2(m+2n)2m-2×(2n+2m)2(n+2m)2n-2=4(m+n)2(m+2n)2m-2(n+2m)2n-2.
In particular,(25)τ(K2[Kn,n])=16×34n-4×n4n-4;n≥1.Theorem 10.
Form,n≥1, we have
(26)τ(K3[Km,n])=34(m+n)4(3m+2n)3n-3(3n+2m)3m-3.Proof.
Applying Lemma1, we have(27)τ(K3[Km,n])=19(m+n)2det(3(m+n)I-D-+A-)=19(m+n)2×det(3n+2m+11⋯10⋯⋯00⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯13n+2m+10⋯⋯00⋯⋯00⋯⋯03m+2n+11⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯13m+2n+10⋯⋯00⋯⋯00⋯⋯03n+2m+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯00⋯⋯01⋯13n+2m+10⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯00⋯⋯03m+2n+11⋯10⋯⋯00⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯13m+2n+10⋯⋯00⋯⋯00⋯⋯03n+2m+11⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯13n+2m+10⋯⋯00⋯⋯00⋯⋯03m+2n+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯00⋯⋯01⋯13m+2n+1)=19(m+n)2(det(3n+2m+11⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯13n+2m+10⋯⋯00⋯⋯03m+2n+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯13m+2n+1))3=19(m+n)2(det(3n+2m+11⋯11⋱⋱⋮⋮⋱⋱11⋯13n+2m+1)m×m)3×(det(3m+2n+11⋯11⋱⋱⋮⋮⋱⋱11⋯13m+2n+1)n×n)3.Using Lemma 2, we have
(28)τ(K3[Km,n])=34(m+n)4(3m+2n)3n-3(3n+2m)3m-3.
In particular,
(29)τ(K3[Kn,n])=64×56n-6×n6n-2;n≥1.


## 5. Complexity of Tensor Product of Graphs

The tensor product, or Kronecker product,G1⊗G2, is the simple graph withV(G1⊗G2)=V1×V2,where(u1,u2)and(v1,v2)are adjacent inG1⊗G2if and only ifu1is adjacent tov1inG1andu2is adjacent tov2inG2[13].Lemma 11.
Form,n≥1, we have
(30)τ(K2⊗Km,n)=0.Theorem 12.
Form,n≥1, we have
(31)τ(K3⊗Km,n)=3×23m+3n-5×n3m-1×m3n-1.Proof.
Applying Lemma1, we have(32)τ(K3⊗Km,n)=19(m+n)2det(3(m+n)I-D-+A-)=19(m+n)2×det(2n+11⋯11⋯⋯11⋯⋯11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯12n+11⋯⋯11⋯⋯11⋯⋯12m+11⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯11⋯12m+10⋯⋯01⋯⋯10⋯⋯02n+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱11⋯⋯10⋯⋯01⋯12n+10⋯⋯01⋯⋯11⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯11⋯⋯11⋯⋯10⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯01⋯⋯10⋯⋯01⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯10⋯⋯00⋯⋯01⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯10⋯⋯01⋯⋯10⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯01⋯⋯11⋯⋯11⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯11⋯⋯10⋯⋯02m+11⋯10⋯⋯01⋯⋯11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯12m+10⋯⋯01⋯⋯10⋯⋯02n+11⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮0⋯⋯01⋯12n+11⋯⋯11⋯⋯11⋯⋯12m+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱11⋯⋯11⋯⋯11⋯12m+1)=19(m+n)2det(ABBBABBBA)=19(m+n)2[det(A-B)]2[det(A+2B)]=19(m+n)2(det(2n0⋯01⋯⋯10⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱0⋮⋱⋱⋮0⋯02n1⋯⋯11⋯⋯12m0⋯0⋮⋱⋱⋮0⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱01⋯⋯10⋯02m))2m×det(2n+33⋯31⋯⋯13⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱3⋮⋱⋱⋮3⋯32n+31⋯⋯11⋯⋯12m+33⋯3⋮⋱⋱⋮3⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱31⋯⋯13⋯32m+3)=19(m+n)2det(ABBTC)×det(DEETF)=19(m+n)2m×(detA)2(det(C-BTA-1B))2×detDdet(F-ETD-1E).Thus,(33)τ(K3⊗Km,n)=19(m+n)2(det(2n0⋯00⋱⋱⋮⋮⋱⋱00⋯02n)m×m)2m×(det(m(4n-1)2n-m2n⋯-m2n-m2n⋱⋱⋮⋮⋱⋱-m2n-m2n⋯-m2nm(4n-1)2n)n×n)2m×det(2n+33⋯33⋱⋱⋮⋮⋱⋱33⋯32n+3)m×mm×det(n(4m+6)+6m2+8m2n+3m6n+8m2n+3m⋯6n+8m2n+3m6n+8m2n+3m⋱⋱⋮⋮⋱⋱6n+8m2n+3m6n+8m2n+3m⋯6n+8m2n+3mn(4m+6)+6m2+8m2n+3m)n×n=19(m+n)2(2n)2m×(-m2n)2n×(det(m(4n-1)-m1⋯11⋱⋱⋮⋮⋱⋱11⋯1m(4n-1)-m)n×n)2×3m×det(2n+331⋯11⋱⋱⋮⋮⋱⋱11⋯12n+33)×(6n+8m2n+3m)n×det(n(4m+6)+6m2+8m6n+8m1⋯11⋱⋱⋮⋮⋱⋱11⋯1n(4m+6)+6m2+8m6n+8m)n×n.
Using Lemma2, we have
(34)τ(K3⊗Km,n)=19(m+n)2(2n)2m×[(m2n)2n×(-3n)2×(-4n)2n-2]×[3m(2n+3m3)×(2n3)m-1]×(6n+8m2n+3m)n×[(4nm+6n+6m2+8m6n+8m+n-1)m×(4nm+6n+6m2+8m6n+8m-1)n-1]=3×(2n)2m-2n×m3n-1×n2n+m-1×25n+m-5=3×23m+3n-5×n3m-1×m3n-1.
In particular,
(35)τ(K3⊗Kn,n)=3×26n-5×n6n-2;n≥1.


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

The symmetric product,G1⊕G2, is the simple graph withV(G1∘G2)=V1×V2,where(u1,u2)and(v1,v2)are adjacent inG1⊕G2if and only if eitheru1is adjacent tov1inG1andu2is not adjacent tov2inG2, oru1is not adjacent tov1inG1andu2is adjacent tov2inG2[13].Theorem 13.
Forn,m≥1, we have
(36)τ(K2⊕Km,n)=(m+n)2(m+n-1).Proof.
Applying Lemma1, we have (37)τ(K2⊕Km,n)=14(m+n)2det(2(m+n)I-D-+A-)=14(m+n)2×det(m+n+11⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1m+n+10⋯⋯00⋯⋯0m+n+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯1m+n+10⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯11⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯00⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯11⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯0m+n+11⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1m+n+10⋯⋯00⋱⋱0m+n+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯1m+n+1)=14(m+n)2det(m+n+11⋯11⋯⋯11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1m+n+11⋯⋯11⋯⋯1m+n+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱11⋯⋯11⋯1m+n+1)m×det(m+n+11⋯1-1⋯⋯-11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯1m+n+1-1⋯⋯-1-1⋯⋯-1m+n+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1-1⋯⋯-11⋯1m+n+1)=14(m+n)2(m+n+1+m+n-1)(m+n+1-1)m+n-1×det(ABBTC)=12(m+n)m+n-2×detAdet(C-BTA-1B)=12(m+n)m+n-2×(2m+n)(m+n)m-1m×det(n2+(3m+1)n+2m2+m(n+2m)n+mn+2m⋯n+mn+2mn+mn+2m⋱⋱⋮⋮⋱⋱n+mn+2mn+mn+2m⋯n+mn+2mn2+(3m+1)n+2m2+m(n+2m))n×n=12(m+n)2m+n-3×(2m+n)×(n+mn+2m)n×det(n2+(3m+1)n+2m2+mn+m1⋯11⋱⋱⋮⋮⋱⋱11⋯1n2+(3m+1)n+2m2+mn+m)n×n.Thus,
(38)τ(K2⊕Km,n)=12(m+n)2m+n-3×(2m+n)×(n+mn+2m)n×(2n+2m)(n+2m)n-1=(m+n)2(m+n-1).In particular,
(39)τ(K2⊕Kn,n)=(2n)2(2n-1);n≥1.Theorem 14.
Form,n≥1, we have
(40)τ(K3⊕Km,n)=3(2m+n)3m-3×(2n+m)3n-3(m2+n2+3mn)2.Proof.
Applying Lemma1, we have(41)τ(K3⊕Km,n)=19(m+n)2det(3(m+n)I-D-+A-)=19(m+n)2×det(2m+n+11⋯10⋯⋯00⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯12m+n+10⋯⋯00⋯⋯00⋯⋯02n+m+11⋯11⋯⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯12n+m+11⋯⋯10⋯⋯01⋯⋯12m+n+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯⋯11⋯12m+n+11⋯⋯10⋯⋯00⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯00⋯⋯00⋯⋯01⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯01⋯⋯10⋯⋯01⋯⋯10⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯00⋯⋯01⋯⋯11⋯⋯10⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮1⋯⋯10⋯⋯01⋯⋯10⋯⋯01⋯⋯10⋯⋯0⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯01⋯⋯10⋯⋯00⋯⋯00⋯⋯01⋯⋯1⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮0⋯⋯00⋯⋯01⋯⋯12n+m+11⋯11⋯⋯10⋯⋯01⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮⋮⋱⋱⋮1⋯12n+m+11⋯⋯10⋯⋯01⋯⋯12m+n+11⋯10⋯⋯0⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯⋯11⋯12m+n+10⋯⋯00⋯⋯00⋯⋯02n+m+11⋯1⋮⋱⋱⋮⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱10⋯⋯00⋯⋯01⋯12n+m+1)=19(m+n)2det(ABBBABBBA)=19(m+n)2[det(A-B)]2[det(A+2B)]=19(m+n)2(det(2m+n+11⋯1-1⋯⋯-11⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯12m+n+1-1⋯⋯-1-1⋯⋯-12n+m+11⋯1⋮⋱⋱⋮1⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1-1⋯⋯-11⋯12n+m+1))2m×det(2m+n+11⋯12⋯⋯21⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱1⋮⋱⋱⋮1⋯12m+n+12⋯⋯22⋯⋯22n+m+11⋯1⋮⋱⋱⋮3⋱⋱⋮⋮⋱⋱⋮⋮⋱⋱12⋯⋯21⋯12n+m+1)=19(m+n)2(det(ABBTC))2×det(DEETF)=19(m+n)2×(detA)2(det(C-BTA-1B))2×detDdet(F-ETD-1E)=(3m+n)2(2m+n)2m-29(m+n)2m×(det(2n2+n(7m+1)+3m2+2mn+3mn+2mn+3m⋯n+2mn+3mn+2mn+3m⋱⋱⋮⋮⋱⋱n+2mn+3mn+2mn+3m⋯n+2mn+3m2n2+n(7m+1)+3m2+2mn+3m)n×n)2m×(3m+n)(2m+n)m-1m×det(2n2+n(7m+1)+3m2-mn+3mn-mn+3m⋯n-mn+3mn-mn+3m⋱⋱⋮⋮⋱⋱n-mn+3mn-mn+3m⋯n-mn+3m2n2+n(7m+1)+3m2-mn+3m)n×n=(3m+n)2(2m+n)2m-29(m+n)2m×(n+2mn+3m)2n(det(2n2+n(7m+1)+3m2+2mn+2m1⋯11⋱⋱⋮⋮⋱⋱11⋯12n2+n(7m+1)+3m2+2mn+2m)n×n)2m×(3m+n)(2m+n)m-1m×(n-mn+3m)ndet(2n2+n(7m+1)+3m2-mn-m1⋯11⋱⋱⋮⋮⋱⋱11⋯12n2+n(7m+1)+3m2-mn-m)n×n.
Using Lemma2, we have
(42)τ(K3⊕Km,n)=19(m+n)2(3m+n)2(2m+n)2m-2×(n+2mn+3m)2n1(n+3m)2n×(3n2+3m2+9nm)2×(2n2+3m2+7nm)2n-2×(3m+n)(2m+n)m-1×(n-mn+3m)n×1(n-m)n×(3n2+3m2+6nm)×(2n2+3m2+7nm)n-1=3(2m+n)3m-3(2n+m)3n-3×(m2+n2+3mn)2.
In particular,
(43)τ(K3⊕Kn,n)=25×36n-5×n6n-2;n≥1.


## 7. Conclusion

The number of spanning treesτ(G)in graphs (networks) is an important invariant. The evaluation of this number is not only interesting from a mathematical (computational) perspective but is also an important measure of reliability of a network and designing electrical circuits. Some computationally hard problems such as the travelling salesman problem can be solved approximately by using spanning trees. 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: 673270-2013-11-27.xml*