# Number of Spanning Trees in the Sequence of Some Graphs

Authors: Jia-Bao Liu; S. N. Daoud
Journal: Complexity
 (2019)

---

## Abstract

In mathematics, one always tries to get new structures from given ones. This also applies to the realm of graphs, where one can generate many new graphs from a given set of graphs. In this work, using knowledge of difference equations, we drive the explicit formulas for the number of spanning trees in the sequence of some graphs generated by a triangle by electrically equivalent transformations and rules of weighted generating function. Finally, we compare the entropy of our graphs with other studied graphs with average degree being 4, 5, and 6.


---

## Body

## 1. Introduction

Deriving closed formulas of the number of spanning trees for various graphs has attracted the attention of a lot of researchers. The importance of this research line is in fact due to the following:(1)
Enumerating specific chemical isomers.(2)
Counting the number of Eulerian circuits in a graph.(3)
Solving some computationally hard problems such as the Steiner tree problem and traveling salesman problem.(4)
Deriving formulas for different type of graphs, which can be helpful in identifying those graphs that contain the maximum number of spanning trees; such investigation has practical consequences related to network reliability [1–12].The number of spanning treesτ(G) of a finite connected undirected graph G is an acyclic (n-1)- edge spanning subgraph.There exist various methods for finding this number. Kirchhoff [13] gave the famous matrix tree theorem: if D is the diagonal matrix of the degrees of G and A denoting the adjacency matrix of G, Kirchhoff matrix L=D-A has all of its cofactors equal to τ(G).Another method to count the complexity of a graph is using Laplacian eigenvalues. LetG be a connected graph with k vertices. Kelmans and Chelnoknov [14] derived the following formula:(1)τG=1k∏i=1k-1μi.where k=μ1≥μ2≥…≥μk=0 are the eigenvalues of the Kirchhoff matrix L.Degenerating the graph through successive elimination of contraction of its edges represents the core of another way to compute the complexity of a graph [15, 16]. If G=(V,E) is a multigraph with e∈E, then G·e is the graph obtained from G by contracting the degree until its endpoints are a single vertex. The formula for computing the number of spanning trees of a multigraph G is given by (2)τG=τG-e+τG·e.This formula is beautiful but not practically useful (it grows exponentially with the size of the graph and may be as many as 2E(G) terms).Many works have conceived techniques to derive the number of spanning tree of a graph which can be found in [17–20].


## 2. Electrically Equivalent Transformations

Kirchhoff's motivation was a study of electrical networks: an edge-weighted graph can be regarded as an electrical network, where weights are the conductance of the respective edges. The effect conductance between two specific verticesx,y can be written as the quotient of (weighted) number of spanning trees and the (weighted) number of so called thickets, i.e., spanning forests with exactly two components and property that each of the components contains precisely one of the vertices x,y [21]. In the following, we list the effect of some simple transformations on the number of spanning trees. Let H be an edge weighted graph, H′ be the corresponding electrically equivalent graph, and τ(H) denote the weighted number of spanning trees H.(i)
Parallel edges: if two parallel edges with conductancesx and y in H are merged into a single edge with conductances x+y in H′, then τ(H′)=τ(H).(ii)
Serial edges: if two serial edges with conductancesx and y in H are merged into a single edge with conductance xy/x+y in H′, then τ(H′)=1/x+yτ(H).(iii)
△-Y transformation: if a triangle with conductances a,b, and c in H is changed into an electrically equivalent star graph with conductances x=ab+bc+ca/a, y=ab+bc+ca/b, and z=ab+bc+ca/c in H′, then τ(H′)=(ab+bc+ca)2/abcτ(H).(iv)
Y-△ transformation: if a star graph with conductances x,y, and z in H is changed into an electrically equivalent triangle with conductances a=yz/x+y+z, b=xz/x+y+z, and c=xy/x+y+z in H′, then τ(H′)=1/x+y+zτ(H).In mathematics one always tries to get new structures from given ones. This also applies to the realm of graphs, where one can generate many new graphs from a given set of graphs. In this work, we compute the number of spanning trees of five sequences of graphs generated by a triangle; we named itGn,An,Bn,Dn, and En, respectively.


## 3. Number of Spanning Trees of the Sequence GraphsGn

Consider the sequence of graphsG1,G2,…,Gn constructed as shown in Figure 1.Figure 1
The first three graphs ofGn.According to the construction, the number of total verticesV(Gn) and edges E(Gn) are V(Gn)=9n-6 and E(Gn)=27n-24, n=1,2,.... It is clear that the average degree of Gn is in the large n limit which is 6.Theorem 1.
Forn≥1, the number of spanning trees in the sequence of the graph Gn is given by (3)2-n+3×5n-3×27n-21475-31206547+2065n+47-2065n1475+31206521309+4320652137+472065n-72n26089+5752065217056923n+1×9n×2137+472065+151+20652137+472065n2Proof.
We use the electrically equivalent transformation to transformGi to Gi-1. Figure 2 illustrates the transformation process from G2 to G1.
Using the properties given in Section2, we have the following the transformations:(4)τH1=127τG2,τH2=τH1,τH3=2a2+124a2+33τH2,τH4=14a2+33τH3,τH5=3a214a2+33τH4,τH6=τH5,τH7=92a2+124a2+3τH6,τH8=4a2+314a2+332a2+1214a2+133τH7,τH9=τH8,τH10=4a2+314a2+13902a2+12τH9,τG1=τH10.Combining these eleven transformations, we have (5)τG2=27014a2+132τG1.Further (6)τGn=∏i=2n27014ai+132τG1=3×270n-1a12∏i=2n14ai+132,where ai-1=34ai+29/14ai+13, i=2,3,…,n.
Its characteristic equation is14λ2-21λ-29=0 which have two roots λ1=21-2065/28 and λ2=21+2065/28. Subtracting these two roots into both sides of ai-1=34ai+29/14ai+13, we get(7)ai-1-21-206528=34ai+2914ai+13-21-206528=329+72065×ai-21-2065/281414ai+13.(8)ai-1-21+206528=34ai+2914ai+13-21+206528=329-72065×ai-21+2065/281414ai+13.Let bi=ai-21-2065/28/ai-21+2065/28. Then by (7) and (8), we get bi-1=2137+472065/72bi and bi=(2137+472065/72)n-ibn.
Therefore(9)ai=2137+472065/72n-i21+2065/28bn-21-2065/282137+472065/72n-ibn-1.Thus(10)a1=2137+472065/72n-121+2065/28bn-21-2065/282137+472065/72n-1bn-1.Using the expression an-1=34an+29/14an+13 and denoting the coefficients of 34an+29 and 14an+13 as αn and βn, we have (11)14an+13=α034an+29+β014an+13,14an-1+13=α134an+29+β114an+13α034an+29+β014an+13,14an-2+13=α234an+29+β214an+13α134an+29+β114an+13,⋮(12)14an-i+13=αi34an+29+βi14an+13αi-134an+29+βi-114an+13,(13)14an-i+1+13=αi+134an+29+βi+114an+13αi34an+29+βi14an+13,(14)⋮14a2+13=αn-234an+29+βn-214an+13αn-334an+29+βn-314an+13,Thus, we obtain(15)τGn=3×270n-1a12αn-234an+29+βn-214an+132where α0=0, β0=1 and α1=14, β1=13. By the expression an-1=34an+29/14an+13 and using (12) and (13), we have(16)αi+1=47αi-36αi-1;βi+1=47βi-36βi-1The characteristic equation of (16) is μ2-47μ+36=0 which have two roots μ1=47+2065/2 and μ2=47-2065/2. The general solutions of (16) are (17)αi=c1μ1i+c2μ2i;βi=d1μ1i+d2μ2i.Using the initial conditions α0=0, β0=1 and α1=14, β1=13 yields(18)αi=2206529547+20652i-2206529547-20652i;βi=295-3206559047+20652i+295+3206559047-20652iIf an=1, it means that Gn is without any electrically equivalent transformation. Plugging (18) into (15), we have(19)τGn=3×270n-1a127965+1712065590×47+20652n-2+7965-1712065590×47-20652n-22,n≥2.When =1, τ(G1)=3 which satisfies (19). Therefore the number of spanning trees in the sequence of the graph Gn is given by(20)τGn=3×270n-1a127965+1712065590×47+20652n-2+7965-1712065590×47-20652n-22,n≥1,where (21)a1=2137+472065/72n-1-1309-432065/1008-21-2065/282137+472065/72n-1-151-2065/144-1,n≥1.Inserting (21) into (20), we obtain the result.Figure 2
The transformations fromG2 to G1.


## 4. Number of Spanning Trees of the Sequence GraphsAn

Consider the sequence of graphsA1,A2,…,An constructed as shown in Figure 3.Figure 3
The first three graphs ofAn.According to the construction, the number of total verticesV(An) and edges E(An) are V(An)=9n-6 and E(An)=27n-24, n=1,2,….It is clear that the average degree ofAn is in the large n limit which is 6.Theorem 2.
Forn≥1, the number of spanning trees in the sequence of the graph An is given by(22)2n-1×33n-4×53n-7-1747+35n55+245+3465-22875322+1445n+297-35n12045+53875229×2n47+215+67+15547+215n2Proof.
We use the electrically equivalent transformation to transformAi to Ai-1. Figure 4 illustrates the transformation process from A2 to A1.
Using the properties given in Section2, we have the following transformations:(23)τH1=127τA2,τH2=τH1,τH3=127τH2,τH4=τH3,τH5=33a2+1τH4,τH6=39a2+133τH5,τH7=τH6,τH8=9a2+13303a2+1τH7,τA1=τH8.Combining these nine transformations, we have (24)τA2=2709a2+132τA1.Further (25)τAn=∏i=2n2709ai+132τA1=3×270n-1a12∏i=2n9ai+132,where ai-1=22ai+29/9ai+13, i=2,3,...,n. Its characteristic equation is 9λ2-9λ-29=0, which have two roots λ1=3-55/6 and λ2=3+55/6. Subtracting these two roots into both sides of ai-1=22ai+29/9ai+13, we get(26)ai-1-3-556=22ai+299ai+13-3-556=57+35×ai-3-55/629ai+13(27)ai-1-3+556=22ai+299ai+13-3+556=57-35×ai-3+55/629ai+13Let bi=ai-3-55/6/ai-3+55/6. Then by (26) and (27), we get bi-1=47+215/2bi and bi=(47+215/2)n-ibn.
Therefore(28)ai=47+215/2n-i3+55/6bn-3-55/647+215/2n-ibn-1.Thus (29)a1=47+215/2n-13+55/6bn-3-55/647+215/2n-1bn-1.Using the expression an-1=22an+29/9an+13 and denoting the coefficients of 22an+29 and 9an+13 as αn and βn we have(30)9an+13=α022an+29+β09an+13,9an-1+13=α122an+29+β19an+13α022an+29+β09an+13,9an-2+13=α222an+29+β29an+13α122an+29+β19an+13,⋮(31)9an-i+13=αi22an+29+βi9an+13αi-122an+29+βi-19an+13,(32)9an-i+1+13=αi+122an+29+βi+19an+13αi22an+29+βi9an+13,(33)⋮9a2+13=αn-222an+29+βn-29an+13αn-322an+29+βn-39an+13,Thus, we obtain(34)τAn=3×270n-1a12αn-222an+29+βn-29an+132,where α0=0,β0=1 and α1=9,β1=13. By the expression an-1=22an+29/9an+13 and (31) and (32), we have (35)αi+1=35αi-25αi-1;βi+1=35βi-25βi-1The characteristic equation of (35) is μ2-35μ+25=0 which have two roots μ1=35+155/2 and μ2=35-155/2. The general solutions of (35) are αi=c1μ1i+c2μ2i; βi=d1μ1i+d2μ2i.
Using the initial conditionsα0=0, β0=1 and α1=9, β1=13 yields(36)αi=352535+1552i-352535-1552i;βi=25-355035+1552i+25+355035-1552i.If an=1, it means that An is without any electrically equivalent transformation. Plugging (36) into (34), we have(37)τAn=3×270n-1a1255+245535+1552n-2+55-245535-1552n-22,n≥2.When n=1, τ(A1)=3 which satisfies (37). Therefore the number of spanning trees in the sequence of the graph An is given by(38)τAn=3×270n-1a1255+245535+1552n-2+55-245535-1552n-22,n≥1.where (39)a1=47+215/2n-1-144-955/87-3-55/647+215/2n-1-67-155/58-1,n≥1.Inserting (39) into (38) we obtain the result.Figure 4
The transformations fromA2 to A1.


## 5. Number of Spanning Trees of the Sequence GraphsBn

Consider the sequence of graphsB1,B2,…,Bn constructed as shown in Figure 5.Figure 5
The first three graphs ofBn.According to the construction, the number of total verticesV(Bn) and edges E(Bn) are V(Bn)=9n-6, E(Bn)=24n-21, n=1,2,…. It is clear that the average degree of Bn in the large n limit is 16/3.Theorem 3.
Forn≥1, the number of spanning trees in the sequence of the graph Bn is given by(40)2-n+7×35n-6×5n-3-15+10511+105n-11-105n15+1052-849+5105113+11105n+8n1337+1311052498n113+11105+211+105113+11105n2Proof.
We use the electrically equivalent transformation to transformBi to Bi-1. Figure 6 illustrates the transformation process from B2 to B1.
Using the properties given in Section2, we have the following the transformations:(41)τH1=127τB2,τH2=τH1,τH3=2a2+12a23τH2,τH4=14a2+33τH3,τH5=3a214a2+33τH4,τH6=τH5,τH7=92a2+124a2+3τH6,τH8=4a2+314a2+332a2+1214a2+133τH7,τH9=τH8,τH10=14a2+134a2+3902a2+12τH9,τB1=τH10.Combining these eleven transformations, we have (42)τB2=27014a2+132τB1.Further (43)τBn=∏i=2n27014ai+132τB1=3×270n-1a12∏i=2n14ai+132,where ai-1=20ai+16/14ai+13, i=2,3,...,n.
Its characteristic equation is14λ2-7λ-16=0 which has two roots λ1=7-3105/28 and λ2=7+3105/28. Subtracting these two roots into both sides of ai-1=20ai+16/14ai+13, we get(44)ai-1-7-310528=20ai+1614ai+13-7-310528=311+105×ai-7-3105/28214ai+13.(45)ai-1-7+310528=20ai+1614ai+13-7+310528=311-105×ai-7+3105/28214ai+13.Let bi=ai-7-3105/28/ai-7+3105/28. Then by (44) and (45), we get bi-1=(113+11105/8)bi and bi=(113+11105/8)n-ibn.
Thereforeai=(113+11105/8)n-i(7+3105/28)bn-7-3105/28/(113+11105/8)n-ibn-1. Thus(46)a1=113+11105/8n-17+3105/28bn-7-3105/28113+11105/8n-1bn-1.Using the expression an-1=20an+16/14an+13 and denoting the coefficients of 20an+16 and 14an+13 as αn and βn, we have(47)14an+13=α020an+16+β014an+13,14an-1+13=α120an+16+β114an+13α020an+16+β014an+13,14an-2+13=α220an+16+β214an+13α120an+16+β114an+13,⋮(48)14an-i+13=αi20an+16+βi14an+13αi-120an+16+βi-114an+13,(49)14an-i+1+13=αi+120an+16+βi+114an+13αi20an+16+βi14an+13,(50)⋮14a2+13=αn-220an+16+βn-214an+13αn-320an+16+βn-314an+13,Thus, we obtain(51)τBn=3×270n-1a12αn-220an+16+βn-214an+132,where α0=0,β0=1 and α1=14,β1=13. By the expression an-1=20an+16/14an+13 and (48) and (49), we have(52)αi+1=33αi-36αi-1;βi+1=33βi-36βi-1The characteristic equation of (52) is μ2-33μ+36=0 which have two roots μ1=33+3105/2 and μ2=33-3105/2. The general solutions of (52) are αi=c1μ1i+c2μ2i; βi=d1μ1i+d2μ2i.
Using the initial conditionsα0=0,β0=1 and α1=14,β1=13 yields(53)αi=21054533+31052i-21054533-31052i;βi=45-1059033+31052i+45+1059033-31052iIf an=1, it means that Bnis without any electrically equivalent transformation. Plugging (53) into (51), we have(54)τBn=3×270n-1a12135+1310510×33+31052n-2+135-1310510×33-31052n-22,n≥2.When n=1, τ(B1)=3 which satisfies (54). Therefore the number of spanning trees in the sequence of the graph Bn is given by(55)τBn=3×270n-1a12135+1310510×33+31052n-2+135-1310510×33-31052n-22,n≥1.where (56)a1=113+11105/8n-1-49-5105/14-7-3105/28113+11105/8n-1-11-105/4-1,n≥1.Inserting (56) into (55), we obtain the result.Figure 6
The transformations fromB2 to B1.


## 6. Number of Spanning Trees of the Sequence GraphsDn

Consider the sequence of graphsD1,D2,…,Dn constructed as shown in Figure 7.Figure 7
The first three graphs ofDn.According to the construction, the number of total verticesV(Dn) and edges E(Dn) are V(Dn)=9n-6, E(Dn)=24n-21, n=1,2,….It is clear that the average degree ofDn in the large n limit is 16/3.Theorem 4.
Forn≥1, the number of spanning trees in the sequence of the graph Dn is given by 2n-3×33n-4×5n-1×1-7×25n-12.Proof.
We use the electrically equivalent transformation to transformDi to Di-1. Figure 8 illustrates the transformation process from D2 to D1.
Using the properties given in Section2, we have the following the transformations:(57)τH1=127τD2,τH2=τH1,τH3=127τH2,τH4=τH3,τH5=33a2+1τH4,τH6=39a2+133τH5,τH7=τH6,τH8=9a2+1330a2+1τH7,τD1=τH8.Combining these nine transformations, we have (58)τD2=2709a2+132τD1.Further (59)τDn=∏i=2n2709ai+132τD1=3×270n-1a12∏i=2n9ai+132,where ai-1=13ai+16/9ai+13, i=2,3,...,n.
Its characteristic equation is9λ2-16=0 which have two roots λ1=-4/3 and λ2=4/3. Subtracting these two roots into both sides of ai-1=13ai+16/9ai+13, we get(60)ai-1+43=13ai+169ai+13+43=25×ai+4/39ai+13(61)ai-1-43=13ai+169ai+13-43=ai-4/39ai+13Let bi=ai+4/3/ai-4/3.. Then by (60) and (61), we get bi-1=25bi and bi=(25)n-ibn.
Thereforeai=(25)n-i(4/3)bn+4/3/(25)n-ibn-1. Thus(62)a1=425n-1bn+1325n-1bn-1.Using the expression an-1=13an+16/9an+13 and denoting the coefficients of 13an+16 and 9an+13 as αn and βn, we have(63)9an+13=α013an+16+β09an+13,9an-1+13=α113an+16+β19an+13α013an+16+β09an+13,9an-2+13=α213an+16+β29an+13α113an+16+β19an+13,⋮(64)9an-i+13=αi13an+16+βi9an+13αi-113an+16+βi-19an+13,(65)9an-i+1+13=αi+113an+16+βi+19an+13αi13an+16+βi9an+13,(66)⋮9a2+13=αn-213an+16+βn-29an+13αn-313an+16+βn-39an+13.Thus, we obtain(67)τDn=3×270n-1a12αn-213an+16+βn-29an+132,where α0=0,β0=1 and α1=9,β1=13. By the expression an-1=13an+16/9an+13 and (64) and (65), we have(68)αi+1=26αi-25αi-1;βi+1=26βi-25βi-1The characteristic equation of (68) is μ2-26μ+25=0 which have two roots μ1=25 and μ2=1. The general solution of (68) is αi=c1μ1i+c2μ2i; βi=d1μ1i+d2μ2i.
Using the initial conditionsα0=0, β0=1 and α1=9, β1=13 yields(69)αi=92425i-1;βi=1225i+1.If an=1, it means that Dn is without any electrically equivalent transformation. Plugging (69) into (67), we have(70)τDn=3×270n-1a12175825n-2+182,n≥2.When =1, τ(D1)=3 which satisfies (70). Therefore the number of spanning trees in the sequence of the given Dn by(71)τDn=3×270n-1a12175825n-2+182,n≥1.where (72)a1=2825n-1-42125n-1+3,n≥1.Inserting (72) into (71), we obtain the result.Figure 8
The transformations fromD2 to D1.


## 7. Number of Spanning Trees of the Sequence GraphsEn

Consider the sequence of graphsE1,E2,...,En constructed as shown in Figure 9.Figure 9
The first three graphs ofEn.According to the construction, the number of total verticesV(En) and edges E(En) are V(En)=9n-6 and E(En)=24n-21, n=1,2,….It is clear that the average degree ofEn in the large n limit is 16/3.Theorem 5.
Forn≥1, the number of spanning trees in the sequence of the graph En is given by (73)16n-36175-99370561+3705n+61-3705n6175+99370523561+5937053713+613705n-8n159171+261537052457567523×8n3713+613705+1051+1737053713+613705n2Proof.
We use the electrically equivalent transformation to transformEi to Ei-1. Figure 10 illustrates the transformation process from E2 to E1.
Using the properties given in Section2, we have the following the transformations:(74)τH1=127τE2,τH2=τH1,τH3=9a2τH2,τH4=13a2+23τH3,τH5=τH4,τH6=3a2+218a2τH5,τH7=τH6,τH8=95a2+33a2+2τH7,τH9=33a2+269a2+433τH8,τH10=τH9,τH11=69a2+43725a2+3τH10,τE1=τH11.Combining these twelve transformations, we have (75)τE2=1669a2+432τE1.Further (76)τEn=∏i=2n1669ai+432τE1=3×16n-1a12∏i=2n[69ai+432,where ai-1=79ai+49/69ai+43, i=2,3,…,n.
Its characteristic equation is69λ2-36λ-49=0 which has two roots λ1=18-3705/69 and λ2=18+3705/69. Subtracting these two roots into both sides of ai-1=79ai+49/69ai+43, we get(77)ai-1-18-370569=79ai+4969ai+43-18-370569=61+3705×ai-18-3705/6969ai+43.(78)ai-1-18+370569=79ai+4969ai+43-18+370569=61-3705×ai-18+3705/6969ai+43.Let bi=ai-18-3705/69/ai-18+3705/69. Then by (77) and (78), we get bi-1=3713+613705/8bi and bi=(3713+613705/8)n-ibn.
Therefore(79)ai=3713+613705/8n-i18+3705/69bn-18-3705/693713+613705/8n-ibn-1.Thus(80)a1=3713+613705/8n-118+3705/69bn-18-3705/693713+613705/8n-1bn-1.Using the expression an-1=79an+49/69an+43 and denoting the coefficients of 79an+49 and 69an+43 as αn and βn, we have(81)69an+43=α079an+49+β069an+43,69an-1+43=α179an+49+β169an+43α079an+49+β069an+43,69an-2+43=α279an+49+β269an+43α179an+49+β169an+43,⋮(82)69an-i+43=αi79an+49+βi69an+43αi-179an+49+βi-169an+43,(83)69an-i+1+43=αi+179an+49+βi+169an+43αi79an+49+βi69an+43,(84)⋮69a2+43=αn-279an+49+βn-269an+43αn-379an+49+βn-369an+43,Thus, we obtain(85)τEn=3×16n-1a12αn-279an+49+βn-269an+432,where α0=0,β0=1 and α1=69,β1=43. By the expression an-1=79an+49/69an+43 and using (82) and (83), we have (86)αi+1=122αi-16αi-1;βi+1=122βi-16βi-1The characteristic equation of (86) is μ2-122μ+16=0 which have two roots μ1=61+3705 and μ2=61-3705. The general solutions of (86) are (87)αi=c1μ1i+c2μ2i;βi=d1μ1i+d2μ2i.Using the initial conditions α0=0,β0=1 and α1=69,β1=43 yields(88)αi=693705741061+3705i-693705741061-3705i;βi=3705-183705741061+3705i+3705+183705741061-3705i.If an=1, it means that En is without any electrically equivalent transformation. Plugging (88) into (85), we have(89)τEn=3×16n-1a1269160+113637051235×61+3705n-2+69160-113637051235×61-3705n-22,n≥2.When n=1, τ(E1)=3 which satisfies (89). Therefore the number of spanning trees in the sequence of the graph En is given by(90)τEn=3×16n-1a1269160+113637051235×61+3705n-2+69160-113637051235×61-3705n-22,n≥1.where (91)a1=3713+613705/8n-13561+593705/-552-18-3705/693713+613705/8n-11051+173705/-184-1,n≥1.Inserting (91) into (90), we obtain the result.Figure 10
The transformations fromE2 to E1.


## 8. Numerical Results

Table1 illustrates some values of the number of spanning trees in the graphs Gn,An,Bn,Dn and En.Table 1
Some values ofτ(Gn), τ(An), τ(Bn), τ(Dn), and τ(En).
n = 1 n = 2 n = 3 n = 4 n = 5 τ ( G n ) 3 3214890 1871115187500 1079470803800601000 622668632269021652430000  τ ( A n ) 3 2106810 677445120000 214885548050625000 68141993033794218750000  τ ( B n ) 3 1049760 290237644800 79619215161600000 21835433330956869120000  τ ( D n ) 3 681210 116226146700 19621772544609000 3311232242985794430000  τ ( E n ) 3 786432 186900480000 44413488256253952 10554053793863002226688


## 9. Spanning Tree Entropy

After having explicit formulas for the number of spanning trees of the sequence of the five graphsGn,An,Bn,Dn, and En, we can calculate its spanning tree entropy Z which is a finite number and a very interesting quantity characterizing the network structure, defined as in [22, 23] as follows.For a graphG, Z(G)=limn→∞⁡ln⁡τ(G)/V(G). (92)ZGn=19ln⁡1352+2ln⁡47+2065=1.473921812.ZAn=19ln⁡6750-2ln⁡47+215+2ln⁡322+1445=1.407443598.ZBn=19ln⁡12152+2ln⁡11+105=1.391308773.ZDn=19ln⁡168750=1.337352623.ZEn=19ln⁡16+2ln⁡61+3705=1.375386375.Now we compare the value of entropy in our graphs with other graphs. It is clear that the entropy of the graph Gn is larger than the entropy of the graph An and they have the entropy smaller than the entropy of the antiprism graph [24] which has entropy 1.5143 and larger than the entropy of the Apollonian graph [25] which has the entropy 1.3540 of the same average degree 6. Also the entropy of the graph Bn is larger than the entropy of the graphs Dn and En of the same average degree 16/3. In addition the entropy of our five graphs is larger than the entropy of fractal scale free lattice [26] which has the entropy 1.040 and two dimensional Sierpinski gasket [27] of the average degree 4 which has the entropy 1.166.


## 10. Conclusions

In this work, we compute the complexity in the sequences of some graphs generated by triangle using electrically equivalent transformations. An advantage of this method lies in the avoidance of laborious computation of Laplacian spectra which is needed for a generic method for determining spanning trees.



---

*Source: 4271783-2019-03-12.xml*