# The Laplacian Spectrum, Kirchhoff Index, and the Number of Spanning Trees of the Linear Heptagonal Networks

Authors: Jia-Bao Liu; Jing Chen; Jing Zhao; Shaohui Wang
Journal: Complexity
 (2022)

---

## Abstract

LetHn be the linear heptagonal networks with 2n heptagons. We study the structure properties and the eigenvalues of the linear heptagonal networks. According to the Laplacian polynomial of Hn, we utilize the method of decompositions. Thus, the Laplacian spectrum of Hn is created by eigenvalues of a pair of matrices: LA and LS of order numbers 5n+1 and 4n+1n!/r!n−r!, respectively. On the basis of the roots and coefficients of their characteristic polynomials of LA and LS, we get not only the explicit forms of Kirchhoff index but also the corresponding total number of spanning trees of Hn.


---

## Body

## 1. Introduction

With the discovery of carbon nanotubes, there has been a practical interest in the study of concerning structures based on hexagon networks. Especially for a class of linear hexagonal networks, Yang [1] and Huang et al. [2], respectively, explored Kirchhoff index and another form multiplicative degree-Kirchhoff index of linear hexagonal networks. Years later, Peng et al. [3] had studied the Kirchhoff index and related spanning trees for the linear phenylenes which are constructed from polyominoes and hexagons. Inspired by [4], the multiplicative version of degree-Kirchhoff index and its numbers of spanning trees of the generalized phenylenes are given. We refer the associated work [5–9], and the notation we use in this paper follows that in [10].Tips of carbon nanotubes are closed by pentagons. Heptagons, which generate negative curvatures, can also be introduced with those pentagons [5]. Additionally, there are abundant practical applications of the heptagons in nature aspects; a remarkable example is that cacti are the most common plants with heptagons in natural structures. In our work, we concern a class of linear heptagonal networks Hn inspired by these linear hexagonal networks (see Figure 1). Evidently, we see that π is an automorphism 1¯,2¯,…n¯,1,1′,2,2′,…,4n+1,4n+1′.Figure 1
Linear heptagonal networksHn.Before proceeding, we shall review some terminologies for the chemical graph theory. Since the topological indices are closely related to the physical and chemical properties of the corresponding molecular graph, the calculation of various topological indices is the core subject of chemical graph theory [11–20]. At this point, we slightly observe some properties of the Kirchhoff index. Klein and Randić in [21] defined a summation of all resistance distances between pairs of vertices from a graph G as its Kirchhoff index KfG, namely,(1)KfG=∑i<jrij,where rij is its resistance distance between two vertices i and j [22–26].Lately, one finds that Kirchhoff index of a graphG is closely related to the Laplacian eigenvalue. That is,(2)KfG=n∑k=2n1μk,in which 0=μ1<μ2≤⋯≤μn are Laplacian eigenvalues of G.The organization of this paper is as follows. In Section2, some necessary notations of the block matrices are reviewed. Then, we apply automorphism and some lemmas into Hn. The Laplacian matrix can be considered to have block matrices, and we can obtain the results of these block matrices. Finally, we use transposition of matrices to get LA and LS. In Section 3, we first study those explicit formulas of Kirchhoff index for Hn. Connecting these eigenvalues of LA and LS, we can obtain the Laplacian spectrum of Hn. In the end, we obtain the number of spanning trees of Hn.


## 2. Preliminaries

Before embarking on the proofs of our main results, we observe a special method that is the basis of our work. These equations that we describe can be found in [5,13].For ann by n matrix M, denote by this submatrix of MMi1,…,ik, and create by the deletion of the i1-th, …, ik-th rows and the columns. In the following part, PMx=detxI−M is this characteristic polynomial of M.Label these vertex sets ofHn by V0=1¯,2¯,…,n¯, V1=1,2,…,4n+1, and V2=1′,2′,…,4n+1′. So, the Laplacian matrix of Hn will be block matrices.(3)LHn=LV0V0LV0V1LV0V2LV1V0LV1V1LV1V2LV2V0LV2V1LV2V2.Note thatLV0V1=LV0V2,LV1V0=LV2V0,LV1V1=LV2V2, and LV1V2=LV2V1.Given(4)T=In00012In12In012In−12In.Consider the unitary transformation ofTLHnT′; then,(5)TLHnT′=LA00LS,where T′ is the transposition of T. Obviously,(6)LA=In2LV0V12LV1V0LV1V1+LV1V2,LS=LV1V1−LV1V2.Furthermore, we present those matrices introduced above in the following. According to the structure of Figure1, one obtains LV0V0=2In.(7)ŁV0V1=lijn×4n+1=00−10000⋯000000000−1⋯0000000000⋯000⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮0000000⋯0000000000⋯−100n×4n+1,where lij=−1 and lij=0; else, j=4i−1.(8)LV1V1=2−1000⋯00000−12−100⋯000000−13−10⋯0000000−12−1⋯00000000−13⋯00000⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮00000⋯3−100000000⋯−12−10000000⋯0−13−1000000⋯00−12−100000⋯000−124n+1×4n+1.In addition, one gets(9)LV1V2=lij4n+1×4n+1=diag−1,0,0,0,−1,…,−1,0,0,0,−1,where l4k+1,4k+1=−1 for k∈0,1,2,…,n; else, it is 0.According to equation (2), one has(10)LV1V1+LV1V2=lij4n+1×4n+1=1−100000⋯0000000−12−10000⋯00000000−13−1000⋯000000000−12−100⋯0000000000−12−10⋯00000000000−12−1⋯000000000000−13⋯0000000⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋮0000000⋯3−1000000000000⋯−12−100000000000⋯0−12−10000000000⋯00−12−1000000000⋯000−13−100000000⋯0000−12−10000000⋯00000−114n+1×4n+1,where l11=l4n+1,4n+1=1, lii=2 with i∈2,4,…,4n and for i≠4k−1, l4k−1,4k−1=3 for k∈1,n. Also, li,i+1=li+1,i=−1 for i∈1,4n and lij=0 with i−j>1.Also,(11)LS=lij4n+1×4n+1=3−1000⋯000−12−100⋯0000−13−10⋯00000−12−1⋯000000−13⋯000⋮⋮⋮⋮⋮⋱⋮⋮⋮00000⋯3−1000000⋯−12−100000⋯0−134n+1×4n+1,where lii=3 for i is odd and lii=2 for i is even; li,i+1=li+1,i=−1 with i∈1,2,3,…,4n, and lij=0 with i−j>1.Next, we list some lemmas that may be useful throughout our main proof.Lemma 1 (see [1]).
Suppose thatLA,LS are mentioned before. We have(12)PLHnx=PLAxPLSx.Based on the properties of these spanning trees and Laplacian eigenvalues, we have the following.Lemma 2 (see [27]).
LetG be connected graph with G=n and τG be the complexity in G. We have(13)τG=1n∏i=2nui.Lemma 3 (see [28]).
LetM1,M2,M3, and M4 be the square matrices with p by p, p by q, q by p, and q by q matrices, respectively. We have(14)detM1M2M3M4=detM1⋅detM4−M3M1−1M2,where M1 is invertible and M4−M3M1−1M2 are denoted as Schur complements of M4.


## 3. Kirchhoff Index and the Number of Spanning Trees ofHn

So far, our first main result provides the exact formula to the Kirchhoff index ofHn. Together with their eigenvalues of LA and LS, it is not hard to use Lemma 1 and obtain Laplacian spectrum of Hn. Our second main result is to furnish the complete information of the number of spanning trees of Hn, which contributed to degree products and their eigenvalues. Suppose 0=α1<α2≤⋯≤α5n+1 and 0<β1≤β2≤⋯≤β4n+1 are, respectively, the roots of PLAx=0 and PLSx=0. By equation (2), one has the following.Lemma 4.
LetHn be the linear heptagonal networks. We have(15)KfHn=9n+2⋅∑i=25n+11αi+∑j=14n+11βj.Obviously, we only need to compute the eigenvalues ofLA and LS. Thus, the formulas of ∑i=25n+11/αi and ∑j=14n+11/βj are given as follows.Lemma 5.
Assume that0=α1<α2≤⋯≤α5n+1 are the eigenvalues of LA. One has(16)∑i=25n+11αi=108n3+66n2+7n+436n+8.Proof.
It is known that(17)PLAx=x5n+1+a1x5n+⋯+a5n−1x2+a5nx=xx5n+a1x5n−1+⋯+a5n−1x+a5n,with a5n≠0. Then, we find that 1/α2,1/α3,…,1/α5n+1 satisfy the equation(18)a5n⋅x5n+a5n−1⋅x5n−1+⋯+a1⋅x+1=0.
In the line with Vieta theorem, it gives(19)∑i=25n+11αi=−15n−1⋅a5n−1−15n⋅a5n.Proposition 1.
−15n⋅a5n=9n+2⋅2n−1.Proof.
Because−15na5n is the summation of these principal minors from LA, that has 5n rows and columns, it is easy to see that(20)−15n⋅a5n=∑i=15n+1detLAi.
In view of equation (2), we know that i can be chosen from the matrix 2In or LV1V1+LV1V2. Hence, we consider the cases below.
(1) Case 1. For the case of 1≤i≤n, LAi is created by dropping the i-th row of matrices 2In and 2LV0V1 and also the related columns of 2In and 2LV1V0. Let 2In−1,Rn−1×4n+1,Rn−1×4n+1′, and U4n+1×4n+1 be these blocks. By using Lemma 3 and fundamental operations, one knows that(21)detLAi=2In−1Rn−1×4n+1Rn−1×4n+1′U4n+1×4n+1=2In−100M1,where M1=U4n+1×4n+1−Rn−1×4n+1′Rn−1×4n+1=mpq, of which m11=m4n+1,4n+1=1,mpp=2 for p∈2,3,…,4n−1,4n, but p≠4i−1, m4i−1,4i−1=3. Also, mp,p+1=mp+1,p=−1 for p∈1,2,…,4n+1 and mpq=0 for p−q>1. By routine calculations, we have(22)detLAi=detM1=2n−1.
(2) Case 2. For the case of n+1≤i≤5n+1, we say LAi is deduced by deleting the i-th row of LV1V1+LV1V2 and 2LV1V0 and the corresponding column of LV1V1+LV1V2 and 2LV0V1. Denote 2In,Rn×4n,Rn×4n′, and U4n×4n as desired blocks. By Lemma 3 and fundamental operations, we obtain that(23)detLAi=2InRn×4nRn×4n′U4n×4n=2In00M2,where M2=U4n×4n−Rn×4n′Rn×4n. Set M2′=mpq with order 4n+1, of which mpp=2 for p∈2,3,4,5,6,7,…,4n−1,4n. Also, m11=m4n+1,4n+1=1, mp,p+1=mp+1,p=−1 for p∈1,4n and mpq=0 with p−q>1. By routine calculations, we have(24)detLAi=2n.Combining equations (4)–(6), we have(25)−15n⋅a5n=∑i=15n+1detLAi=∑i=1ndetLAi+∑i=n+15n+1detLAi=n⋅2n−1+4n+1⋅2n=9n+2⋅2n−1.So, the proof of Proposition1 is finished.Next, we will focus on recursive calculations for−15n−1a5n−1.Proposition 2.
−15n−1a5n−1=108n3+66n2+7n+4⋅2n−3Proof.
We know that−15n−1a5n−1 is the summation of their principal minors of LA giving 5n−1 rows and columns. We can obtain(26)−15n−1⋅a5n−1=∑i=15n+1detLAi,j.
For the result of Proposition1, we will consider the following cases.
(1) Case 1. For the case of 1≤i<j≤n, we see that LAi,j is obtained by dropping i and j rows of the identity matrices 2In and 2LV0V1 and the corresponding columns of 2In and 2LV1V0. Denote 2In−2,Rn−2×4n+1,Rn−2×4n+1′, and U4n+1×4n+1 as desired blocks. Based on Lemma 3 and elementary operations, we have(27)detLAi,j=2In−2Rn−2×4n+1Rn−2×4n+1′U4n+1×4n+1=2In−200M3,where M3=U4n+1×4n+1−Rn−2×4n+1′Rn−2×4n+1=mpq, of which m11=m4n+1,4n+1=1,mpp=2 for p∈2,3,4,5,6,7,…,4n−1,4n and p≠4i−1; also, p≠4j−1, m4i−1,4i−1=m4j−1,4j−1=3. Then, mp,p+1=mp+1,p=−1 with p∈1,2,3,…,4n−1,4n, mpq=0 with p−q>1. By basic calculations, we have(28)detLAi,j=detM3=4⋅j−i+2⋅2n−2.
(2) Case 2. For the case of n+1≤i<j≤5n+1, we say that LAi,j is created by dropping i−n-th and j−n-th rows of LV1V1+LV1V2 and 2LV1V0 and the corresponding columns of LV1V1+LV1V2 and 2LV0V1. Denote 2In,Rn×4n−1,Rn×4n−1′, and U4n−1×4n−1 as desired blocks. In terms of Lemma 3 and fundamental operations, we obtain(29)detLAi,j=2InRn×4n−1Rn×4n−1′U4n−1×4n−1=2In00M4,where M4=U4n−1×4n−1−Rn×4n−1′Rn×4n−1=M2′i−n,j−n. By recursive calculations, we obtain(30)detLAi,j=j−1−n2n−2,ifi=n+1,j=n+k,2≤k≤4n;5n−i+12n,ifj=5n+1,i=n+k,2≤k≤4n;j−i2n,ifn+2≤i<j≤5n.
(3) Case 3. We consider the case of 1≤i≤n, n+1≤j≤5n+1. In other words, we have that LAi,j is created by dropping i rows of the identity matrices 2In and 2LV0V1 and j−n-th rows of 2LV1V0 and LV1V1+LV1V2, respectively. For further consideration, we write them as 2In, 2LV1V0, LV1V1+LV1V2 and 2LV0V1. Denote 2In−1,Rn−1×4n,Rn−1×4n′, and U4n×4n as desired blocks. By the methods of Lemma 3 and fundamental operations, we have(31)detLAi,j=2In−1Rn−1×4nRn−1×4n′U4n×4n=2In00M5,where. By an explicit calculation, we get(32)detLAi,j=j−4i+1−n+1⋅2n−1.Considering equations (7)–(10), one acquires(33)−15n−1a5n−1=∑1≤i≤j5n+1detLAi,j=∑1≤i≤jndetLAi,j+∑n+1≤i≤j5n+1detLAi,j+∑1≤i≤n,n+1≤j≤5n+15n+1detLAi,j=4n3+6n2−7n6⋅2n−2+256n3+192n2+32n6⋅2n−2+64n3−4n+126⋅2n−2=108n3+66n2+7n+4⋅2n−3.Corollary 1.
Suppose that0=α1<α2≤⋯≤α5n+1 are the roots of PLAx=0. Then,(34)∑i=25n+11αi=108n3+66n2+7n+436n+8.
LetPLsx=detxI−Ls=x4n+1+b1x4n+⋯+b4nx+c4n+1. By using the relation between the coefficients and roots of PLsx, it is not hard to see that(35)∑j=14n+11βj=−14nb4n−14n+1b4n+1=−14nb4ndetLs.On the other hand, we will consideri-th ordered principal submatrix, Mi, which is found by giving first i rows and columns of Ls,i=1,2,…,n−1. Let mi=detMi.Fact 1.
For1≤i≤4n,(36)mi=1+322+62i+1−322−62i,ifiis even;6+3242+62i+−6+3242−62i,ifiis odd.Proof. We will compute and obtain that m1=3,m2=5,m3=12,m4=19. For 3≤i≤4n, we can extend detMi with its last row as follows:(37)mi=2mi−1−mi−2,ifiis  even;3mi−1−mi−2,ifiis  odd.
For1≤i≤2n, let ei=m2i, and for 1≤i≤2n−1, let fi=m2i+1. Then we have, together with (12), ei=5, fi=12, and for i≥2,(38)ei=2fi−1−ei−1,ifiis  even;fi=3ei−fi−1,ifiis  odd.
From the first equation in (13), one has fi−1=ei/2+ei−1/2; therefore, fi=ei+1/2+ei/2. Replacing fi−1 and fi into the second equation in (13) yields ei+1=4ei−ei−1, i≥2. Similarly, we obtain fi+1=4fi−fi−1, i≥2. Thus, mi meets the recurrence relation(39)m1=3,m2=5,m3=12,m4=19,mi=4ei−2−ei−4,i≥5.
So, we see that the characteristic equation of (40) is x4=4x2−1, whose roots are x1=2+6/2, x2=−2+6/2, x3=2−6/2, and x4=−2+6/2.
Assume that the general solution of (14) is(40)mi=2+62iy1+−2+62iy2+2−62iy3+−2−62iy4.
Combining the initial condition in (14), the system of equations is given:(41)2+62y1+−2+62y2+2−62y3+−2−62y4=3;2+622y1+−2+622y2+2−622y3+−2−622y4=5;2+623y1+−2+623y2+2−623y3+−2−623y4=12;2+624y1+−2+624y2+2−624y3+−2−624y4=19.
The unique solution of this system of equation isy1=2+6+23+32/8, y2=2−6+23−32/8, y3=2−6−23+32/8, and y4=2+6−23−32/8. Therefore, Fact 1 is deduced by (15).
By using the expansion formula, one can deducedetLs with its last row below LS=3M4n−M4n−1.Combining it with Fact 1, the following is obtained.Fact 2.
detLs=3+232+64n+3−232−64n/24n+1.
Now we are ready to determineb4n. We can denote this diagonal of detLs by lii,i∈1,2n+1.Fact 3.
b4n=120n+603n+6+53+6+732−34n2+64n+120n−603n+6−53+6−732+34n2−64n/24⋅24nProof.
Sinceb4n=−14nb4n is the summation of these principal minors from Ls with size 4n by 4n, we have(42)b4n=∑i=14n+1detLSi=∑i=14n+1detMi−100B1=∑i=14n+1detMi−1detB1,where(43)B1=li+1,i+1−1⋯0⋮⋱⋮⋮0⋯l4n,4n−10⋯−1l4n+1,4n+1.
Because permutating rows and related columns in square matrices keeps its determinant unchanged, combining it withLS, we will get detB1=detM4n+1−i. Therefore,(44)b4n=∑i=14n+1mi−1m4n+1−i=2m4n+∑k=12n−1m2km4n−2k+∑k=12nm2l−1m4n−2l+1⋅put:m0=1.
By Fact 1, we have that2m4n=1+32+6/24n+1−32−6/24n and(45)∑k=12n−1m2km4n−2k=∑k=12n−11+322+622k+1−322−622k×1+322+624n−2k+1−322−624n−2k=48n+243n−18−163+6+432−34n2+64n24·24n+48n−243n−18+163+6−432+34n2−64n24·24n.
We can use a similar routine to obtain(46)∑l=12nm2l−1m4n−2l+1=∑l=12n6+3242+622l−1+−6+342−622l−1×6+3242+624n−2l+1+−6+3242−624n−2l+1=72n+363n−33+9+632−34n+12+64n24·24n+72n−363n+33+9−632+34n+12−64n24·24n.Lemma 6.
For graphHn,(47)KfHn=20n+2⋅108n3+66n2+7n+436n+8+−14n⋅b4ndetLs,where −1b4n=120n+603n+6+53+6+732−34n2+64n+120n−603n+6−53+6−732+34n2−64n/24⋅24n, detLs=3+232+64n+3−232−64n/24n+1.The Kirchhoff indices of linear heptagonal networks fromH1 to H50 are denoted in Table 1.Table 1
Kirchhoff indices of linear heptagonal networks fromH1 to H50.
HnKfHnHnKfHnHnKfHnHnKfHnHnKfHnH179.25H1141 172.05H21268 961.03H31845 446.16H411932 627.45H2404.17H1252 876.62H22308 245.21H32928 509.96H422075 670.87H31138.09H1366 610.15H23351 178.36H331016 842.73H432225 603.25H42442.97H1482 534.64H24397 922.47H341110 606.45H442382 586.59H54480.81H15100 812.10H25448 639.54H351209 979.64H452546 782.89H67413.61H16121 604.52H26503 491.58H361315 074.79H462718 354.15H711 403.37H17145 073.90H27562 640.57H371426 103.39H472897 462.38H816 612.10H18171 382.24H28626 248.53H381543 210.96H483084 269.56H923 201.79H19200 691.54H29694 477.44H391666 559.50H493278 937.71H1031 334.44H20233 163.80H30767 489.32H401796 310.99H503481 628.82Lemma 7.
For graphHn,(48)τLn=3+232+64n+3−232−64n23n+2.Proof.
By Lemma2, we have τG=1/n∏i=2nui. Note that(49)∏i=25n+1αi=−15na5n=9n+22n−1,∏j=14n+1βj=detLs=3+232+64n+3−232−64n24n+1.
Then,(50)τHn=3+232+64n+3−232−64n23n+2.
Next, the number of spanning trees in linear heptagonal networks fromH1 to H12 is given in Table 2.Table 2
The number of spanning trees of linear heptagonal networks fromH1 to H12.
HnτHnHnτHnHnτHnHnτHnH145H4973 080H721 034 100 000H10454 673 000 000 000H21254H527 106 500H8585 934 000 000H1112 665 600 000 000 000H334 932H6755 090 000H916 322 000 000 000H12352 817 000 000 000 000



---

*Source: 5584167-2022-01-04.xml*