# The Kirchhoff Index of Toroidal Meshes and Variant Networks

Authors: Jia-Bao Liu; Xiang-Feng Pan; Jinde Cao; Xia Huang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The resistance distance is a novel distance function on electrical network theory proposed by Klein and Randić. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices in G. In this paper, we established the relationships between the toroidal meshes network Tm×n and its variant networks in terms of the Kirchhoff index via spectral graph theory. Moreover, the explicit formulae for the Kirchhoff indexes of L(Tm×n), S(Tm×n), T(Tm×n), and C(Tm×n) were proposed, respectively. Finally, the asymptotic behavior of Kirchhoff indexes in those networks is obtained by utilizing the applications of analysis approach.


---

## Body

## 1. Introduction

Throughout this paper we are concerned with finite undirected connected simple graphs (networks). LetG=(V,E) be a graph with vertices labelled 1,2,…,n. The adjacency matrix A(G) of G is an n×n matrix with the (i,j)-entry equal to 1 if vertices i and j are adjacent and 0 otherwise. Suppose D(G)=diag⁡(d1(G),d2(G),…,dn(G)) is the degree diagonal matrix of G, where di(G) is the degree of the vertex i, i=1,2,…,n. Let L(G)=D(G)-A(G) be called the Laplacian matrix of G. Then, the eigenvalues of A(G) and L(G) are called eigenvalues and Laplacian eigenvalues of G, respectively.Given graphsG and H with vertex sets U and V, the Cartesian product G□H of graphs G and H is a graph such that the vertex set of G□H is the Cartesian product U×V; and any two vertices (u,u′) and (v,v′) are adjacent in G□H if and only if either u=v and u′ is adjacent with v′ in H or u′=v′ and u is adjacent with v in G [1]. It is well known that many of the graphs (networks) operations can produce a great deal of novel types of graphs (networks), for example, Cartesian product of graphs, line graph, subdivision graph, and so on. The clique-inserted graph, denoted by C(G), is defined as a line graph of the subdivision graph S(G) [2, 3]. The subdivision graph of an r-regular graph is (r,2)-semiregular graph. Consequently, the clique-inserted graph of an r-regular graph is the line graph of an (r,2)-semiregular graph.The resistance distances between verticesi and j, denoted by rij, are defined as the effective electrical resistance between them if each edge of G is replaced by a unit resistor [4]. A famous distance-based topological index, the Kirchhoff index Kf(G), is defined as the sum of resistance distances between all pairs of vertices in G; that is, Kf(G)=(1/2)∑i=1n‍∑j=1n‍rij(G), known as the Kirchhoff index of G [4]; recently, this classical index has also been interpreted as a measure of vulnerability of complex networks [5].The Kirchhoff index attracted extensive attention due to its wide applications in physics, chemistry, graph theory, and so forth [6–13]. Besides, the Kirchhoff index also is a structure descriptor [14]. Unfortunately, it is rather hard to directly design some algorithms [15–17] to calculate resistance distances and the Kirchhoff indexes of graphs. So, many researchers investigated some special classes of graphs [18–21]. In addition, many efforts were also made to obtain the Kirchhoff index bounds for some graphs [17, 22]. Details on its theory can be found in recent papers [17, 22] and the references cited therein.Motivated by the above results, we present the corresponding calculating formulae for the Kirchhoff index ofL(Tm×n), S(Tm×n), T(Tm×n), and C(Tm×n) in this paper. The rest of this paper is organized as follows. Section 2 presents some underlying notations and preliminaries in our discussion. The proofs of our main results and some asymptotic behavior of Kirchhoff index are proposed in Sections 3 and 4, respectively.


## 2. Notations and Some Preliminaries

In this section, we introduced some basic properties which we need to use in the proofs of our main results. Suppose thatTm×n stands for the graphs Cm□Cn for the convenience of description. It is trivial for m,n are 1, 2, without loss of generality, we discuss the situations for any positive integer m,n≥3.Zhu et al. [15] and Gutman and Mohar [8] proved the relations between Kirchhoff index of a graph and Laplacian eigenvalues of the graph as follows.Lemma 1 (see [8, 15]).
LetG be a connected graph with n≥2 vertices and let μ1≥μ2≥⋯≥μn=0 be the Laplacian eigenvalues of graph G; then
(1)Kf(G)=n∑i=1n-1‍1μi.The line graph of a graphG, denoted by L(G), is the graph whose vertices correspond to the edges of G with two vertices of L(G) being adjacent if and only if the corresponding edges in G share a common vertex. The subdivision graph of a graph G, denoted by S(G), is the graph obtained by replacing every edge in G with a copy of P2 (path of length two). The total graph of a graph G, denoted by T(G), is the graph whose vertices correspond to the union of the set of vertices and edges of G, with two vertices of T(G) being adjacent if and only if the corresponding elements are adjacent or incident in G. Let PG(x) be the characteristic polynomial of the Laplacian matrix of a graph G; the following results were shown in [23].Lemma 2 (see [23]).
LetG be an r-regular connected graph with n vertices and m edges; then(2)PL(G)(x)=(x-2r)m-nPG(x),PS(G)(x)=(-1)m(2-x)m-nPG(x(r+2-x)),PT(G)(x)=(-1)m(r+1-x)n(2r+2-x)m-nPG(x(r+2-x)r-x+1),
where PL(G)(x), PS(G)(x), and PT(G)(x) are the characteristic polynomials for the Laplacian matrix of graphs L(G), S(G), and T(G), respectively.A bipartite graphG with a bipartition V(G)=(U,V) is called an (r,s)-semiregular graph if all vertices in U have degree r and all vertices in V have degree s. Apparently, the subdivision graph of an r-regular-graph G is (r,2)-semiregular graph.Lemma 3 (see [24]).
LetG be an (r,s)-semiregular connected graph with n vertices. Then
(3)PL(G)(x)=(-1)n(x-(r+s))m-nPG(r+s-x),
where PL(G)(x) is the Laplacian characteristic polynomial of the line graph L(G) and m is the number of edges of G.Lemma 4 (see [23]).
LetG be a connected simple r-regular graph with n vertices and m edges and let L(G) be the line graph of G. Then
(4)Kf(L(G))=r2Kf(G)+14n(m-n).Lemma 5 (see [23]).
LetG be a connected simple r-regular graph with n≥2 vertices; then
(5)Kf(S(G))=(r+2)22Kf(G)+(r2-4)n2+4n8.The following lemma gives an expression onKf(T(G)) and Kf(G) of a regular graph G.Lemma 6 (see [25]).
LetG be a r-regular connected graph with n vertices and m edges, and r≥2; then
(6)Kf(T(G))=n(r+2)(r+4)2(r+3)∑i=1n-1‍1μi+3+r+(r+2)22(r+3)Kf(G)+n2(r2-4)8(r+1)+n2.Lemma7 presents the formula for calculating Kirchhoff index of Tm×n; in the following proof, some techniques in [26] are referred to.Lemma 7 (see [26]).
For the toroidal networksTm×n with any positive integer m,n≥3,
(7)Kf(Tm×n)=mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+nm3-m12+mn3-n12.Proof.
Suppose the Laplacian eigenvalues ofCm and Cn are 4sin2⁡(iπ/m) and 4sin2⁡(jπ/n), i=0,1,…,m-1; j=0,1,…,n-1; then the Cartesian product G□H and the Laplacian eigenvalues of L(cm□Cn) are
(8)4sin2⁡iπm+4sin2⁡jπn,i=0,1,…,m-1;j=0,1,…,n-1.
According to Lemma1, the Kirchhoff index of the toroidal networks Kf(Tm×n) is
(9)Kf(Tm×n)=mn∑(i,j)∈A×B∖{(0,0)}‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n),A={0,1,…,m-1},B={0,1,…,n-1}=mn∑i=0m-1‍∑j=0n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n),hhhhhhhhhhhhhhhhhW(i,j)≠(0,0)(10)=mn(∑i=1m-1‍14sin2⁡(iπ/m)+∑j=1n-1‍14sin2⁡(jπ/n)hhhhh+∑i=1m-1‍∑j=1n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n))=n(m∑i=1m-1‍14sin2⁡(iπ/m))+m(n∑j=1n-1‍14sin2⁡(jπ/n))+mn∑i=1m-1‍∑j=1n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n)=nKf(Cm)+mKf(Cn)+mn∑i=1m-1‍∑j=1n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n)=mn∑i=1m-1‍∑j=1n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n)+nm3-m12+mn3-n12.
SinceKf(Cn)=(n3-n)/12, (10) in the last line holds.
The following consequence was presented in [26]. Here we give a short proof.Lemma 8 (see [26]).
For the toroidal networksTm×n with any positive integer m,n≥3,
(11)lim⁡m→∞lim⁡n→∞Kf(Tm×n)m2n2≈1.905.Proof.
By virtue of (9), one can derive that
(12)Kf(Tm×n)mn=∑i=0m-1∑j=0n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n),000000000000000000000000000(i,j)≠(0,0).
Hence,
(13)lim⁡m→∞lim⁡n→∞Kf(Tm×n)m2n2=lim⁡m→∞lim⁡n→∞1mn∑i=0m-1∑j=0n-1‍14-2cos⁡⁡(2πi/m)-2cos⁡⁡(2πj/n),hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh(i,j)≠(0,0)=12π12π∫02π∫02πdxdy4-2cos⁡⁡x-2cos⁡⁡y≈1.905.


## 3. Main Results

### 3.1. The Kirchhoff Index ofL(Tm×n)

In the following theorem, we proposed the formula for calculating the Kirchhoff index of the line graph ofTm×n, denoted by Kf(L(Tm×n)).Theorem 9.
LetL(Tm×n) be line graphs of Tm×n with any positive integer m,n≥3; then
(14)Kf(L(Tm×n))=2mn∑i=1m-1∑j=1n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n)+nm3-m6+mn3-n6+m2n24.Proof.
Apparently the toroidal networksTm×n are 4-regular graphs which have mn vertices and 2mn edges, respectively.
We clearly obtained the following relationshipKf(L(Tm×n)) and Kf(Tm×n) from Lemma 4:
(15)Kf(L(Tm×n))=r2Kf(Tm×n)+(r-2)m2n28=2Kf(Tm×n)+m2n24.
Substituting the results of Lemma7 into (15), we can get the formula for the Kirchhoff index of Kf(L(Tm×n)),
(16)Kf(L(Tm×n))=2mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+nm3-m6+mn3-n6+m2n24,
which completes the proof.


### 3.2.  The Kirchhoff Index ofS(Tm×n)

In an almost identical way as Theorem9, we derived the formula for the Kirchhoff index on the subdivision graph of Tm×n, denoted by Kf(S(Tm×n)).Theorem 10.
LetS(Tm×n) be subdivision graphs of Tm×n with any positive integer m,n≥3; then
(17)Kf(S(Tm×n))=18mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3nm3-m2+3mn3-n2+3m2n2+mn2.Proof.
Noting thatTm×n are 4-regular graphs which have mn vertices, we clearly obtained from Lemma 5(18)Kf(S(Tm×n))=(r+2)22Kf(Tm×n)+(r2-4)m2n2+4mn8=18Kf(Tm×n)+3m2n2+mn2.
Together with the results of Lemma7 and (18), we can get the formula for the Kirchhoff index on the subdivision graph of Tm×n:
(19)Kf(S(Tm×n))=18mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3nm3-m2+3mn3-n2+3m2n2+mn2.
The proof is completed.


### 3.3.  The Kirchhoff Index ofT(Tm×n)

Now we proved the formula for estimating the Kirchhoff index in the total graph ofTm×n, denoted by Kf(T(Tm×n)).Theorem 11.
LetT(Tm×n) be total graphs of Tm×n with any positive integer m,n≥3; then
(20)Kf(T(Tm×n))=187mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+314n(m3-m)+314m(n3-n)+3m2n210+mn2,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhi(i,j)≠(0,0).Proof.
Supposing that the Laplacian eigenvalues ofL(Cm□Cn) are μij, one can readily see that
(21)μij=4sin2⁡iπm+4sin2⁡jπn,i=0,1,…,m-1;j=0,1,…,n-1.
Applying Lemma6, the following result is straightforward:
(22)Kf(T(Tm×n))=187Kf(Tm×n)+3m2n210+mn2+24mn7∑(i,j)≠(0,0)17+μij.
Notice thatL(Cm□Cn) have mn-1 nonzero Laplacian eigenvalues, and
(23)∑(i,j)≠(0,0)17+μij=∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n),(i,j)≠(0,0),
where i=0,1,…,m-1 and j=0,1,…,n-1.
Consequently, the relationships betweenTm×n and its variant networks T(Tm×n) for Kirchhoff index are as follows:
(24)Kf(T(Tm×n))=187Kf(Tm×n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3m2n210+mn2,(i,j)≠(0,0).
According to the results of Lemma7, we can verify the formula for the Kirchhoff index of the total graph of Kf(T(Tm×n)) from (24). Consider
(25)Kf(T(Tm×n))=187mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+314n(m3-m)+314m(n3-n)+3m2n210+mn2,(i,j)≠(0,0).
This completes the proof of Theorem 11.


### 3.4.  The Kirchhoff Index ofC(Tm×n)

We will explore the formula for estimating the Kirchhoff index in the clique-inserted graph ofTm×n, denoted by Kf(C(Tm×n)).Theorem 12.
LetC(Tm×n) be clique-inserted graphs of Tm×n with any positive integer m,n≥3; then
(26)Kf(C(Tm×n))=4mn∑i=0m-1∑j=0n-113-5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+4mn∑i=0m-1∑j=0n-113+5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+53m2n2,
where the first summation i=0,1,…,m-1; j=0,1,…,n-1, and (i,j)≠(0,0).Proof.
Noting thatS(Tm×n) is (r,2)-semiregular graphs and supposing that S(Tm×n)has  p vertices and q edges, then obviously p=3mn, q=4mn, and r=4, respectively.
By virtue of Lemma3,
(27)PL(G)(x)=(-1)n(x-(r+s))m-nPG(r+s-x).
Let G be the graph S(Tm×n); that is,
(28)PL(S(Tm×n))(x)=(-1)p(x-(r+s))q-pPS(Tm×n)(r+s-x).
From the definition of clique-inserted graph, one can immediately obtain that
(29)PC(Tm×n)(x)=(-1)p(x-(r+2))q-pPS(Tm×n)(6-x)=(-1)3mn(x-6)mnPS(Tm×n)(6-x).
Obviously, it follows from Lemma2,
(30)PS(G)(x)=(-1)m(2-x)m-nPG(x(r+2-x)).
Replace x with 6-x in (30); moreover, Tm×n have mn vertices and 2mn edges; we have that
(31)PS(Tm×n)(6-x)=(-1)mn(x-4)mnPTm×n(x(6-x)).
Based on (29) and (31),
(32)PC(Tm×n)(x)=(-1)4mn((x-4)(x-6))mnPTm×n(x(6-x)).
Since the roots of x(6-x)=μij are
(33)3±9-μij,
where μij are the Laplacian eigenvalues of Tm×n and μij=4sin2⁡(iπ/m)+4sin2⁡(jπ/n), i=0,1,…,m-1; j=0,1,…,n-1.
It follows from (32) that the Laplacian spectrum of C(Tm×n) is
(34)SpecL(C(Tm×n))=(46μij(C(Tm×n))μij′(C(Tm×n))mnmn11),
where μij(C(Tm×n))=3-9-μij, μij′(C(Tm×n))=3+9-μij, i=0,1,…,m-1, and j=0,1,…,n-1.
Employing Lemma1, (33), and the Laplacian spectrum of C(Tm×n), the following result is straightforward:
(35)Kf(C(Tm×n))=4mn(mn4+mn6+∑(i,j)≠(0,0)‍1μij(C(G))+∑‍1μij′(C(G)))=53m2n2+4mn(∑(i,j)≠(0,0)‍13-9-μij00000000000000000+∑‍13+9-μij∑(i,j)≠(0,0)‍13-9-μij)=4mn∑i=0m-1∑j=0n-113-5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n),hhhhhhhhhhhhhhhhhhhhhhhhhhh0000(i,j)≠(0,0),+4mn∑i=0m-1∑j=0n-113+5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+53m2n2.
Hence Theorem 12 holds.Remark 13.
The consequences of Lemma7 and Theorems 9–12 above present closed-form formulae for immediately obtaining its Kirchhoff indexes in terms of finite various networks; however, the quantities are rather difficult to calculate directly.


## 3.1. The Kirchhoff Index ofL(Tm×n)

In the following theorem, we proposed the formula for calculating the Kirchhoff index of the line graph ofTm×n, denoted by Kf(L(Tm×n)).Theorem 9.
LetL(Tm×n) be line graphs of Tm×n with any positive integer m,n≥3; then
(14)Kf(L(Tm×n))=2mn∑i=1m-1∑j=1n-1‍14sin2⁡(iπ/m)+4sin2⁡(jπ/n)+nm3-m6+mn3-n6+m2n24.Proof.
Apparently the toroidal networksTm×n are 4-regular graphs which have mn vertices and 2mn edges, respectively.
We clearly obtained the following relationshipKf(L(Tm×n)) and Kf(Tm×n) from Lemma 4:
(15)Kf(L(Tm×n))=r2Kf(Tm×n)+(r-2)m2n28=2Kf(Tm×n)+m2n24.
Substituting the results of Lemma7 into (15), we can get the formula for the Kirchhoff index of Kf(L(Tm×n)),
(16)Kf(L(Tm×n))=2mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+nm3-m6+mn3-n6+m2n24,
which completes the proof.


## 3.2.  The Kirchhoff Index ofS(Tm×n)

In an almost identical way as Theorem9, we derived the formula for the Kirchhoff index on the subdivision graph of Tm×n, denoted by Kf(S(Tm×n)).Theorem 10.
LetS(Tm×n) be subdivision graphs of Tm×n with any positive integer m,n≥3; then
(17)Kf(S(Tm×n))=18mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3nm3-m2+3mn3-n2+3m2n2+mn2.Proof.
Noting thatTm×n are 4-regular graphs which have mn vertices, we clearly obtained from Lemma 5(18)Kf(S(Tm×n))=(r+2)22Kf(Tm×n)+(r2-4)m2n2+4mn8=18Kf(Tm×n)+3m2n2+mn2.
Together with the results of Lemma7 and (18), we can get the formula for the Kirchhoff index on the subdivision graph of Tm×n:
(19)Kf(S(Tm×n))=18mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3nm3-m2+3mn3-n2+3m2n2+mn2.
The proof is completed.


## 3.3.  The Kirchhoff Index ofT(Tm×n)

Now we proved the formula for estimating the Kirchhoff index in the total graph ofTm×n, denoted by Kf(T(Tm×n)).Theorem 11.
LetT(Tm×n) be total graphs of Tm×n with any positive integer m,n≥3; then
(20)Kf(T(Tm×n))=187mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+314n(m3-m)+314m(n3-n)+3m2n210+mn2,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhi(i,j)≠(0,0).Proof.
Supposing that the Laplacian eigenvalues ofL(Cm□Cn) are μij, one can readily see that
(21)μij=4sin2⁡iπm+4sin2⁡jπn,i=0,1,…,m-1;j=0,1,…,n-1.
Applying Lemma6, the following result is straightforward:
(22)Kf(T(Tm×n))=187Kf(Tm×n)+3m2n210+mn2+24mn7∑(i,j)≠(0,0)17+μij.
Notice thatL(Cm□Cn) have mn-1 nonzero Laplacian eigenvalues, and
(23)∑(i,j)≠(0,0)17+μij=∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n),(i,j)≠(0,0),
where i=0,1,…,m-1 and j=0,1,…,n-1.
Consequently, the relationships betweenTm×n and its variant networks T(Tm×n) for Kirchhoff index are as follows:
(24)Kf(T(Tm×n))=187Kf(Tm×n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3m2n210+mn2,(i,j)≠(0,0).
According to the results of Lemma7, we can verify the formula for the Kirchhoff index of the total graph of Kf(T(Tm×n)) from (24). Consider
(25)Kf(T(Tm×n))=187mn∑i=1m-1∑j=1n-114sin2⁡(iπ/m)+4sin2⁡(jπ/n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+314n(m3-m)+314m(n3-n)+3m2n210+mn2,(i,j)≠(0,0).
This completes the proof of Theorem 11.


## 3.4.  The Kirchhoff Index ofC(Tm×n)

We will explore the formula for estimating the Kirchhoff index in the clique-inserted graph ofTm×n, denoted by Kf(C(Tm×n)).Theorem 12.
LetC(Tm×n) be clique-inserted graphs of Tm×n with any positive integer m,n≥3; then
(26)Kf(C(Tm×n))=4mn∑i=0m-1∑j=0n-113-5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+4mn∑i=0m-1∑j=0n-113+5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+53m2n2,
where the first summation i=0,1,…,m-1; j=0,1,…,n-1, and (i,j)≠(0,0).Proof.
Noting thatS(Tm×n) is (r,2)-semiregular graphs and supposing that S(Tm×n)has  p vertices and q edges, then obviously p=3mn, q=4mn, and r=4, respectively.
By virtue of Lemma3,
(27)PL(G)(x)=(-1)n(x-(r+s))m-nPG(r+s-x).
Let G be the graph S(Tm×n); that is,
(28)PL(S(Tm×n))(x)=(-1)p(x-(r+s))q-pPS(Tm×n)(r+s-x).
From the definition of clique-inserted graph, one can immediately obtain that
(29)PC(Tm×n)(x)=(-1)p(x-(r+2))q-pPS(Tm×n)(6-x)=(-1)3mn(x-6)mnPS(Tm×n)(6-x).
Obviously, it follows from Lemma2,
(30)PS(G)(x)=(-1)m(2-x)m-nPG(x(r+2-x)).
Replace x with 6-x in (30); moreover, Tm×n have mn vertices and 2mn edges; we have that
(31)PS(Tm×n)(6-x)=(-1)mn(x-4)mnPTm×n(x(6-x)).
Based on (29) and (31),
(32)PC(Tm×n)(x)=(-1)4mn((x-4)(x-6))mnPTm×n(x(6-x)).
Since the roots of x(6-x)=μij are
(33)3±9-μij,
where μij are the Laplacian eigenvalues of Tm×n and μij=4sin2⁡(iπ/m)+4sin2⁡(jπ/n), i=0,1,…,m-1; j=0,1,…,n-1.
It follows from (32) that the Laplacian spectrum of C(Tm×n) is
(34)SpecL(C(Tm×n))=(46μij(C(Tm×n))μij′(C(Tm×n))mnmn11),
where μij(C(Tm×n))=3-9-μij, μij′(C(Tm×n))=3+9-μij, i=0,1,…,m-1, and j=0,1,…,n-1.
Employing Lemma1, (33), and the Laplacian spectrum of C(Tm×n), the following result is straightforward:
(35)Kf(C(Tm×n))=4mn(mn4+mn6+∑(i,j)≠(0,0)‍1μij(C(G))+∑‍1μij′(C(G)))=53m2n2+4mn(∑(i,j)≠(0,0)‍13-9-μij00000000000000000+∑‍13+9-μij∑(i,j)≠(0,0)‍13-9-μij)=4mn∑i=0m-1∑j=0n-113-5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n),hhhhhhhhhhhhhhhhhhhhhhhhhhh0000(i,j)≠(0,0),+4mn∑i=0m-1∑j=0n-113+5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+53m2n2.
Hence Theorem 12 holds.Remark 13.
The consequences of Lemma7 and Theorems 9–12 above present closed-form formulae for immediately obtaining its Kirchhoff indexes in terms of finite various networks; however, the quantities are rather difficult to calculate directly.


## 4. The Asymptotic Behavior of Related Kirchhoff Index

We explore the asymptotic behavior of Kirchhoff index for the investigated networks above asm,n tend to infinity. It is interesting and surprising that the quantity tends to a constant even though Kf(G)→∞, as m,n tend to infinity; that is,
(36)lim⁡m→∞lim⁡n→∞Kf(G)m2n2=C,m,n⟶∞.
Moreover, one can employ the applications of analysis approach to obtain the explicit approximate values of Kirchhoff index for the related networks.Theorem 14.
LetL(Tm×n) be line graphs of Tm×n with any positive integer m,n; then
(37)lim⁡m→∞lim⁡n→∞Kf(L(Tm×n))m2n2≈4.060.Proof.
According to (15) and the result of Lemma 8, we can derive that
(38)Kf(L(Tm×n))=2Kf(Tm×n)+m2n24=4.060m2n2.
Consequently,
(39)lim⁡m→∞lim⁡n→∞Kf(L(Tm×n))m2n2≈4.060.
The result is equivalent toL(Tm×n) having asymptotic Kirchhoff index,
(40)Kf(L(Tm×n))≈4.060m2n2,m,n⟶∞.Theorem 15.
LetS(Tm×n) be subdivision graph of Tm×n with any positive integer m,n; then
(41)lim⁡m→∞lim⁡n→∞Kf(S(Tm×n))m2n2≈35.790.Proof.
Similarly, according to (18), we can easily verify that
(42)Kf(S(Tm×n))=18Kf(Tm×n)+3m2n2+mn2=35.790m2n2.
Hence,
(43)lim⁡m→∞lim⁡n→∞Kf(S(Tm×n))m2n2≈35.790.Theorem 16.
LetT(Tm×n) be total graph of Tm×n with any positive integer m,n≥3; then
(44)lim⁡m→∞lim⁡n→∞Kf(T(Tm×n))m2n2≈5.521.Proof.
Consider the summation term∑i=0m-1‍∑j=0n-1‍(1/(7+4sin2⁡(iπ/m)+4sin2⁡(jπ/n))).
Since(45)lim⁡m→∞lim⁡n→∞1m1n∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)=lim⁡m→∞lim⁡n→∞1m1n∑i=0m-1‍∑j=0n-1‍111-2cos⁡⁡(2πi/m)-2cos⁡⁡(2πj/n)=14π2∫02π∫02πdxdy11-2cos⁡⁡x-2cos⁡⁡y≈0.094.
The value in last line via the mathematic software MATLAB, which can obtain the result above.
Combining with (22), we can obtain that
(46)Kf(T(Tm×n))=187Kf(Tm×n)+24mn7∑i=0m-1∑j=0n-117+4sin2⁡(iπ/m)+4sin2⁡(jπ/n)+3m2n210+mn2,(i,j)≠(0,0)≈5.521m2n2.
So
(47)lim⁡m→∞lim⁡n→∞Kf(T(Tm×n))m2n2≈5.521.Theorem 17.
LetC(Tm×n) be clique-inserted graph of Tm×n with any positive integer m,n≥3; then
(48)lim⁡m→∞lim⁡n→∞Kf(C(Tm×n))m2n2≈38.591.Proof.
From the proof of Theorem12, we know that
(49)Kf(C(Tm×n))=4mn∑i=0m-1∑j=0n-113-5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+4mn∑i=0m-1∑j=0n-113+5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)+53m2n2,
where the first summation i=0,1,…,m-1; j=0,1,…,n-1, and (i,j)≠(0,0).
Asm,n tend to infinity, it follows from the first summation term:
(50)lim⁡m→∞lim⁡n→∞1m1n∑i=0m-1∑j=0n-113-5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)=14π2∫02π∫02πdxdy3-5+2cos⁡⁡x+2cos⁡⁡y≈9.037.
Similarly, it holds from the second summation term when m,n tend to infinity,
(51)lim⁡m→∞lim⁡n→∞1m1n∑i=0m-1∑j=0n-113+5+2cos⁡⁡(2πi/m)+2cos⁡⁡(2πj/n)=14π2∫02π∫02πdxdy3+5+2cos⁡⁡x+2cos⁡⁡y≈0.195.
Combining with the consequences of Theorem 12 and (50) and (51), it follows that
(52)lim⁡m→∞lim⁡n→∞Kf(C(Tm×n))m2n2≈38.591.
Summing up, we complete the proof.


## 5. Conclusions

Resistance distance was introduced by Klein and Randic´ as a generalization of the classical distance. In this paper, we have deduced the relationships between the toroidal meshes network Tm×n and its variant networks in terms of the Kirchhoff index via spectral graph theory. The explicit formulae for calculating the Kirchhoff indexes of L(Tm×n), S(Tm×n), T(Tm×n), and C(Tm×n) were proposed for any positive integer m,n≥3, respectively.The asymptotic behavior of Kirchhoff indexes has been investigated with the applications of analysis approach, and the explicit approximate values are obtained by calculations for the related networks. The values of Kirchhoff indexes with respect to various networks can be immediately obtained via this approach; however, the quantities are rather difficult to calculate directly.



---

*Source: 286876-2014-06-03.xml*