# Resistance Distance and Kirchhoff Index for a Class of Graphs

Authors: WanJun Yin; ZhengFeng Ming; Qun Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

LetG[F,Vk,Hv] be the graph with k pockets, where F is a simple graph of order n≥1, Vk={v1,v2,…,vk} is a subset of the vertex set of F, Hv is a simple graph of order m≥2, and v is a specified vertex of Hv. Also let G[F,Ek,Huv] be the graph with k edge pockets, where F is a simple graph of order n≥2, Ek={e1,e2,…ek} is a subset of the edge set of F, Huv is a simple graph of order m≥3, and uv is a specified edge of Huv such that Huv-u is isomorphic to Huv-v. In this paper, we derive closed-form formulas for resistance distance and Kirchhoff index of G[F,Vk,Hv] and G[F,Ek,Huv] in terms of the resistance distance and Kirchhoff index F, Hv and F, Huv, respectively.


---

## Body

## 1. Introduction

There are many theories and methods for studying complex networks. Scholars describe and display complex networks from various angles and strive to discover new phenomena and new features of complex networks. The topology and measurement properties of the network are important research contents of network science. Traditional network indicators include network diameter, point connectivity, edge connectivity, algebraic connectivity, and spectral radius. These indicators can only measure local indicators of the network and have certain limitations on the overall performance of the network.Each network can be thought of as a system that is connected by a number of nodes in some way. The terminology and symbolic representation of graph theory can describe various parameters and structural characteristics in the network accurately and concisely. The nodes in the network are represented by abstract points, and the connections between nodes are used to represent the connections between nodes in the network. The resistance distance can be viewed as a distance measurement on the network and it is also an important invariant of the network. As with the shortest path length, the resistance distance can also characterize the network to some extent. Using the index of resistance distance in the graph theory, it is more convenient to study the network. The Kirchhoff index is the sum of the resistance distances between all pairs of vertices in the graph. The Kirchhoff index has a wide range of applications in physics, chemistry, and network science. In the case of a physical resistance network, the Kirchhoff index describes the average electrical energy consumed when the resistor network is arbitrarily injected; mathematically, the resistance distance is a function of the distance defined on the graph and is the invariant of the graph. At a given network scale, the smaller the Kirchhoff index is [1–3], the better the network coherence is. The smaller the resistance distance between any two nodes, the less the average power consumed by the entire network, and the more the network connectivity.By introducing the resistance distance and the Kirchhoff index into the network research, it can not only enrich and develop the theoretical research of graph theory, but also play an auxiliary role in the quantitative analysis and optimization design of the network.Resistance distance and Kirchhoff index have wide applications in network centrality, network connectivity, random walk algorithm, and robustness [4, 5]. Compared with traditional metrics, resistance distance and Kirchhoff, the advantage of the index is that it can better reflect the integrity and connectivity of the network. With these two quantities, we can optimize the network. It can be seen that the calculation of the resistance distance and the Kirchhoff index is of great significance.Throughout this paper, we consider only finite simple graphs. All graphs considered are simple and undirected graphs. The resistance distance between verticesu and v of G was defined by Klein and Randic [6] to be the effective resistance between nodes u and v as computed with Ohm’s law when all the edges of G are considered to be unit resistors. The Kirchhoff index Kf(G) was defined in [6] as Kf(G)=∑u≤vruv(G), where ruv(G) denote the resistance distance between u and v in G. However, the resistance distance and Kirchhoff index of the graph are, in general, a difficult thing from the computational point of view. Therefore, the bigger the graph, the more difficult it is to compute the resistance distance and Kirchhoff index, so a common strategy is to consider complex graph as composite graph and to find relations between the resistance distance and Kirchhoff indices of the original graphs.LetG=(V(G),E(G)) be a graph with vertex set V(G) and edge set E(G). Let di be the degree of vertex i in G and DG=diag(d1,d2…dV(G)) the diagonal matrix with all vertex degrees of G as its diagonal entries. For a graph G, let AG and BG denote the adjacency matrix and vertex-edge incidence matrix ofG, respectively. The matrix LG=DG-AG is called the Laplacian matrix of G, where DG is the diagonal matrix of vertex degrees of G. We use u1(G)≥u2(G)≥⋯un(G)=0 to denote the eigenvalues of LG. For other undefined notations and terminology from graph theory, the readers may refer to [7] and the references in [5, 8–11].Barik [12] described the Laplacian spectrum of graph with pockets except n+k Laplacian eigenvalues. Nath and Paul [8] gave the Laplacian spectrum of graph with edge pockets except n+k Laplacian eigenvalues. Tian [9] gave the spectrum and signless Laplacian spectrum of graph with pockets and edge pockets except n+k Laplacian eigenvalues. Motivated by these, we will continue to study resistance distance and Kirchhoff index of graphs. This paper considers the resistance distance and Kirchhoff index of graphs with pockets and edge pockets of these two new graph operations below, which come from [12] and [3, 8], respectively.Definition 1 (see [12]).
LetF, Hv be graphs of ordersn andm, respectively, where m≥2,v is a specified vertex of Hv, and Vk={v1,v2,…vk} is a subset of the vertex set of F. Let G=G[F,Vk,Hv] be the graph obtained by taking one copy of F and k vertex disjoint copies of Hv and then attaching thei-th copy of Hv to the vertex vi,  i=1,…k, at the vertexv of H (identify vi with the vertex v of thei-th copy). Then the copies of the graph Hv that are attached the vertices vi,  i=1,…k, are referred to as pockets, and G is described as a graph with k pockets.Definition 2 (see [8]).
LetF and Huv be two graphs of ordersnandm, respectively, where n≥2, m≥3Ek={e1,e2,…,ek} is a subset of the edge set of F, and Huv has a specified edge uv such that Huv-u is isomorphic to Huv-v. Assume that Fs denotes the subgraph of F induced by Ek. Let G=G[F,Ek,Huv] be the graph obtained by taking one copy of F and k vertex disjoint copies of Huv and then pasting the edge uv in thei-th copy of Huv with the edge ei∈Ek, wherei = 1,…k. Then the copies of the graph Huv that are pasted to the edges ei,  i=1,…k, are called edge pockets, and G is described as a graph with k edge pockets.Note that if a copy ofHv is attached to every vertex of F, each at the vertex v of Hv, that is, if G hasn pockets, then the graph G=G[F,Vk,Hv] is nothing but the corona F∘H. If a copy of Huv is pasted to every edge of F, each at the edge uv of Huv, that is, if G hasmedge pockets, then the graph G=G[F,Ek,Huv] is nothing but the edge corona F⋄H, where H=Huv-{u,v}.Recently, Nath and Paul [3] have described the L-spectrum of G=G[F,Ek,Huv] using the L-spectra of F and Hv, when the specified verticesu andv are of degreem-1, and the subgraph Fs of F induced by Ek is regular. Similarly, they also describe the A-spectrum, when H=Huv-{u,v} is regular. In that case, If a copy of Huv is pasted to every edge of F, each at the edge uv of Huv, that is, if G hasnedge pockets, then the graph G=G[F,En,Huv] is nothing but the edge corona F⋄H, where H=Huv-{u,v}. Then the complete L-spectrum of G is described using the L-spectra of F and H when F is regular [4]; if F is a regular graph and H is also a regular graph or a complete bipartite graph, then the complete A-spectrum and Q-spectrum of G are described using the respective A-spectra and Q-spectra of F and H. Buetal investigated resistance distance in subdivision-vertex join and subdivision-edge join of graphs [13]. Liu et al. [14, 15] gave the resistance distance and Kirchhoff index of R-vertex join and R-edge join of two graphs.Motivated by these researches, we obtain formulas for resistance distances and Kirchhoff indexG=G[F,Vk,Hv] and G=G[F,Ek,Huv] in terms of the resistance distance and Kirchhoff index of F,Hv and F,Huv.


## 2. Preliminaries

In this section, we present some preliminary results which will be needed to prove our main results.The1-inverse ofM is a matrixXsuch thatM XM =M. IfM is singular, then it has infinite 1-inverse [1, 4]. For a square matrixM, the group inverse ofM, denoted by M#, is the unique matrixX such thatMXM = M,XMX = X, and MX=XM. It is known that M# exists if and only if rank(M)=rank(M2) ([1, 4, 13, 14, 16]). IfM is real symmetric, then M# exists and M# is a symmetric 1- inverse ofM. Actually, M# is equal to the Moore-Penrose inverse ofM sinceMis symmetric [16, 17].It is known that resistance distances in a connected graphG can be obtained from any 1-inverse of G ([5, 7]). We use M(1) to denote any 1-inverse of a matrix M, and let (M)uv denote the(u, v)- entry ofM.Cui and Tian introduced a new invariant, theM-coronal ΓM(x) of a matrixM of ordern. It is defined to be the sum of the entries of the matrix (xIn-M)-1; that is, ΓM(x)=1nT(xIn-M)-11n, where 1n denotes the column vector of sizen with all the entries equal to one and 1n is the identity matrix of ordern. It is proved that ifM is a matrix of order n with each row sum equal to a constant t, then ΓM(x)=n/x-t. Let A=(aij) and B=(bij) be m×n and p×q matrices, respectively. Then theKronecker product of A and B is defined to the mn×pq partition matrix (aijB) and is denoted by A⊗B. For some properties of theKronecker product of matrices, let G1 and G2 be two graphs with disjoint vertex sets V(G1),V(G2) and edge sets E(G1),E(G2), respectively. The join G1∨G2 of G1 and G2 is the graph union G1∪G2 together with all the edges joining V(G1),V(G2).Lemma 3 (see [7, 16]).
LetG be a connected graph. Then(1)ruvG=L1Guu+L1Gvv-L1Guv-L1Gvu=L#Guu+L#Gvv-2L#Guv.Let1n denote the column vector of dimensionn with all the entries equal to one. We will often use 1 to denote all-ones column vector if the dimension can be read from the context.Lemma 4 (see [10]).
For any graph, we haveLG#1=0.Lemma 5 (see [2]).
Let(2)M=ABCD
be a nonsingular matrix. IfA andD are nonsingular, then(3)M-1=A-1+A-1BS-1CA-1-A-1BS-1-S-1CA-1S-1=A-BD-1C-1-A-1BS-1-S-1CA-1S-1where S=D-CA-1B.Lemma 6 (see [18]).
LetG be a connected graph onn vertices. Then(4)KfG=ntrLG1-1TLG11=ntrLG#.Lemma 7.
Let(5)L=ABBTD
be the Laplacian matrix of a connected graph. IfD is nonsingular, then(6)X=H#-H#BD-1-D-1BTH#D-1+D-1BTH#BD-1is a symmetric 1-inverse ofL, where H=A-BD-1BT.Throughout this paper, assume thatF is a simple graph of ordern and Hv and Huv two simple graphs of orderm, unless mentioned otherwise. We also assume that the specified vertexv in Hv is of degreem−1and the specified verticesu andv in Huv are all of degree m-1. Let H1=Hv-v.H2=Huv-u,v.ThenHv=v∨H1 and Huv=(u,v,uv)∨H2.


## 3. The Resistance Distance and Kirchhoff Index ofG[F,Vk,Hv],  G[F,Ek,Huv]

Firstly, we focus on determining the resistance distance and Kirchhoff index ofG[F,Vk,Hv] in terms of the resistance distance and Kirchhoff index of F,Hv.Theorem 8.
LetF,Hv be graphs of ordersn andm, respectively, where m≥2,v is a specified vertex of Hv, and Vk=v1,v2,…vk is a subset of the vertex set of F. Let G=G[F,Vk,Hv] be the graph as defined in Definition 1. Then G=G[F,Vk,Hv] have the resistance distance and Kirchhoff index as follows:(a) For anyi,j∈ V (F), we have(7)rijGF,Vk,Hv=L#Fii+L#Fjj-2L#Fij.(b) For anyi,j∈ V (H), we have(8)rijGF,Vk,Hv=LH+Im-1-1ii+LH+Im-1-1jj-2LH+Im-1-1ij.(c) For anyi∈ V (G), j ∈ V (H), we have(9)rijGF,Vk,Hv=(L#Hii+LH+Im-1-1⊗Ikjj-2L#Fij.(d)(10)KfGF,Vk,Hv=n+km-1(1nKfF+k∑i=1m-11uiH+1+tr1m-1⊗0TIkTL#F1m-1T⊗0TIk-1T1m-1T⊗0TIkL#F1m-1T⊗0TIk1-km-1.Proof.
Sincev is of degreem−1, Hv can be written as Hv=v∨H, where H is the graph obtained from Hv; after deleting the vertex v and the edges incident to it, the Laplacian matrix of G=G[F,Vk,,Hv] can be written as follows.(11)LG=LF+00T0m-1Ik-1m-1T⊗0TIk-1m-1⊗0TIkTLH+Im-1⊗IkBy Lemma 7, we have(12)H=LF+00T0m-1Ik--1m-1T⊗0TIk(LH+Im-1⊗Ik-1-1m-1⊗0TIkT=LF+00T0m-1Ik-1m-1T(LH+1-11m-1⊗00T0Ik=LF+00T0m-1Ik-00T0m-1Ik=LF,so H#=L(F#).
According to Lemma7, we calculate -H#BD-1and -D-1BTH#.(13)-H#BD-1=-L#F-1m-1T⊗0TIkLH+Im-1⊗Ik-1=L#F1m-1T⊗0TIk.
And(14)-D-1BTH#=-LH+Im-1⊗Ik-1-1m-1⊗0TIkTL#F=1m-1⊗0IkL#F.
We are ready to compute theD-1BTH#BD-1.(15)D-1BTH#BD-1=LH+Im-1-1⊗Ik-1m-1⊗0T-IkTL#F-1m-1T⊗0T-IkLH+Im-1-1⊗Ik=1m-1⊗0TIkTL#F1m-1T⊗0TIk.
Let(16)P=LH+Im-1⊗Ik,M=1m-1⊗0TIkTL#F1m-1T⊗0TIk.
Based on Lemma7, the following matrix(17)N=L#FL#F1m-1T⊗0TIk1m-1⊗0IkL#FP-1+M
is a symmetric1-inverse of G=G[F,Vk,Hv].
For anyi,j∈ V (F), by Lemma 3 and (17), we have(18)rijGF,Vk,Hv=L#Fii+L#Fjj-2L#Fij
as stated in (a).
For anyi,j∈ V (H), by Lemma 3 and (17), we have(19)rijGF,Vk,Hv=LH+Im-1-1⊗Ikii+LH+Im-1-1⊗Ikjj-2LH+Im-1-1⊗Ikij,as stated in (b).
For anyi∈ V (F), j ∈ V (H), by Lemma 3 and (17), we have(20)rijGF,Vk,Hv=(LFii+LH+Im-1-1⊗Ikjj-2L#Fij,as stated in (c).
By Lemma6, we have the following.(21)KfGF,Vk,Hv=n+km-1trN-1TN1=n+km-1trL#F+trLH+Im-1-1⊗Ik))+tr1m-1⊗0T1kTL#F1m-1T⊗0T1k-1TN1
Note that the eigenvalues of(L(H)+I) are u1(H)+1,…um-2(H)+1,um-1(H)+1. Then we have the following.(22)trLH+Im-1-1⊗Ik=k∑i=1m-11uiH+1
LetP=(L(H)+Im-1)⊗Ik; then(23)1TP-11=1m-1T1m-1T…1m-1TP-100…00P-10…000……0000…P-11m-11m-1…1m-1=k1m-1TLH+Im-1-11m-1=km-1.Plugging (22) and (23) into Kf(G[F,Vk,Hv]), we obtain the required result in (d).And then, the same, we focus on determining the resistance distance and Kirchhoff index ofG[F,Ek,Huv] in terms of the resistance distance and Kirchhoff index of F,Huv.LetF and Huv be two graphs of ordersn andm, respectively, where n≥2,m≥3,Ek=e1,e2,…ek is a subset of the edge set ofF, and Huv has a specified edgeuvsuch that Huv-u is isomorphic to Huv-v. Let Fs be an r-regular subgraph of F induced by Ek in Definition 2. Also let G=G[F,Ek,Huv] and |Ek|=k. Then G=G[F,Ek,Huv] have the resistance distance and Kirchhoff index as follows:(e) For anyi,j∈ V (F), we have(24)rijGF,Ek,Huv=LF+m-22LFs000ii#+LF+m-22LFs000jj#-2LF+m-22LFs000ij#.(f) For anyi,j∈ V (H), we have(25)rijGF,Ek,Huv=LH+2Im-2-1⊗Ikii+LH+2Im-2-1⊗Ikjj-2LH+2Im-2-1⊗Ikij.(g) For anyi∈ V (G),j ∈ V (H), we have(26)rijGF,Ek,Huv=LF+m-22LFS000ii#+LH+2Im-2-1⊗Ikjj-2LF+m-22LFS000ij#.(h)(27)KfGF,Ek,Huv=n+km-2trLF+m-22LFs000#+k∑i=1m-21uiH+2+14tr1m-2⊗-RTFs0LFm-22LFs000#1m-2T⊗-RFs0-1T1m-2⊗RTFs0LFm-22LFs000#+1m-2T⊗RFs01-k2m-2.Proof.
LetFs be an r-regular subgraph ofF on the firstpvertices. Then the Laplacian matrix of G=G[F,Ek,Huv] can be written as(28)LG=LF+rm-2Ip0001m-2T⊗-RFs01m-2⊗-RTFs0LH+2Im-2⊗Ik.By Lemma 7, we have(29)H=LF+rm-2Ip000-1m-2T⊗-RFs0(LH+21m-2⊗Ik-11m-2⊗-RTFs0=LF+rm-2Ip000-1m-2TLH+21m-2-11m-2⊗RFsRFsT000=LF+rm-2Ip000-m-22rIp+AFs000=LF+m-22LFs000,so(30)H#=LF+m-22LFs000#.
According to Lemma7, we calculate -H#BD-1and -D-1BTH#.(31)-H#BD-1=-H#1m-2T⊗-RFs0LH+2Im-2⊗Ik-1)=12H#1m-2T⊗RFs0.And(32)-D-1BTH#=-LH+2Im-2⊗Ik-11m-2⊗-RFs0H#=121m-2⊗-RFs0)H#.We are ready to compute the D-1BTH#BD-1(33)D-1BTH#BD-1=-121m-2⊗RTFS0H#1m-2TLH+2Im-2-1)⊗-RFS0=141m-2⊗-RTFS0H#1m-2T⊗-RFS0.Let P=(L(H)+2Im-2)⊗Ik, Q=1m-2T⊗R(Fs)0. Based on Lemma 7, the following matrix(34)N=LF+m-22LFs000#12LF+m-22LFs000#Q12QTLF+m-22LFs000#P-1+14QTLF+m-22LFs000#Qis a symmetric 1-inverse of G[F,Ek,Huv].
For anyi,j ∈V (F), by Lemma 3, we have(35)rijGF,Ek,Huv=LF+m-22LFs000ii#+LF+m-22LFs000jj#-2LF+m-22LFs000ij#,as stated in (e).
For anyi,j ∈V (H), by Lemma 3, we have(36)rijGF,Ek,Huv=LH+2Im-2-1⊗Ikii+LH+2Im-2-1⊗Ikjj-2LH+2Im-2-1⊗Ikij,
as stated in (f).
For anyi∈V (F), j∈(H), we have(37)rijGF,Ek,Huv=LF+m-22LFs000ii#+LH)+2Im-2-1⊗Ikjj-2LF+m-22LFs000ij#,as stated in (g).
By Lemma6, we have(38)KfGF,Ek,Huv=n+km-2trN-1TN1=n+km-2tr(LF+m-22LFs000#+trLH+2Im-2-1⊗Ik+14tr(1m-2⊗-RTFs0H#1m-2T⊗-RFs0-1TN1.Note that the eigenvalues of (L(H)+2Im-2)⊗Ik are u1(H)+2,u2(H)+2,…,um-1(H)+2. Then(39)trLH+2Im-2⊗Ik=k∑i=1m-21uiH+2.Let P=(L(H)+2Im-2)⊗Ik, then(40)1TP-11=1m-2T1m-2T⋯1m-2TP-100⋯00P-10⋯000⋯⋯0000⋯P-11m-21m-2⋯1m-2=k1m-2TLH+2Im-2-11m-2=k2m-2.
Plugging (39) and (40) into KfGF,Ek,Huv, we obtain the required result in (h).


## 4. Conclusion

For complex networks, resistance distance and Kirchhoff index are very important physical quantities. With these two quantities, the network topology can be optimized, making the network design mathematically based. This paper gives the resistance distance and Kirchhoff index calculation formula of the pocket diagram by strict mathematical push.



---

*Source: 1028614-2018-12-26.xml*