# Further Results on Resistance Distance and Kirchhoff Index in Electric Networks

Authors: Qun Liu; Jia-Bao Liu; Jinde Cao
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

In electric circuit theory, it is of great interest to compute the effective resistance between any pairs of vertices of a network, as well as the Kirchhoff index. LetQ(G) be the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. The set of such new vertices is denoted by I(G). The Q-vertex corona of G1 and G2, denoted by G1⊙QG2, is the graph obtained from vertex disjoint Q(G1) and VG1 copies of G2 by joining the ith vertex of V(G1) to every vertex in the ith copy of G2. The Q-edge corona of G1 and G2, denoted by G1⊖QG2, is the graph obtained from vertex disjoint Q(G1) and IG1 copies of G2 by joining the ith vertex of I(G1) to every vertex in the ith copy of G2. The objective of the present work is to obtain the resistance distance and Kirchhoff index for composite networks such as Q-vertex corona and Q-edge corona networks.


---

## Body

## 1. Introduction

For decades we want to know what a graph looks like. We want to reveal the principles of the networks behaviour covered by their complex topology and dynamics. We want to learn about how the network structure evolves over time and how it affects the properties of the dynamic processes on it. Klein and Randić [1] introduced a new distance function named resistance distance based on electric network theory; the resistance distance between vertices vi and vj, denoted by rG(vi,vj), is defined to be the effective electrical resistance between them if each edge of G is replaced by a unit resistor. Resistance distance is an important character of a graph, which can imply many of its dynamic properties. The Kirchhoff index of G  is the sum of resistance distances between all pairs of vertices of G. The Kirchhoff index of a network denotes the mean first-passage time measuring the efficiency of random walks; see [1]. The resistance distance and the Kirchhoff index attracted extensive attention due to its wide applications in complex network, physics, chemistry, and others. For more information on resistance distance and Kirchhoff index of graphs, the readers are referred to [2–22] and the references therein. In view of the applications of the resistance distance and the Kirchhoff index, it is of great interest to calculate this parameter for composite networks and find possible relations between the resistance distance and Kirchhoff indexes of the original networks and those of their composite networks; see, for instance, [3].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 let DG=diag(d1,d2,…,d|V(G)|) be 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 of G, 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 μ1(G)≥u2(G)≥⋯≥μn(G)=0 to denote the eigenvalues of LG. Let l(G) be the line graph of G.The{1}-inverse of M is a matrix X such that MXM=M. If M is singular, then it has infinite many {1}-inverses [6]. We use M(1) to denote any {1}-inverse of a matrix M, and let (M)uv denote the (u,v)-entry of M. For a square matrix M, the group inverse of M, denoted by M#, is the unique matrix X such that MXM=M, XMX=X, and MX=XM. It is known that M# exists if and only if rank(M)=rank(M2) [6, 9]. If M is real symmetric, then M# exists and M# is a symmetric {1}-inverse of M. Actually, M# is equal to the Moore-Penrose inverse of M since M is symmetric [9]. It is known that resistance distances in a connected graph G can be obtained from any {1}-inverse of G [7, 8].For a graphG, let Q(G) be the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. Let I(G) be the set of newly added vertices; that is, I(G)=V(Q(G))∖V(G). Next, we define two new operations as follows.LetG1 and G2 be two vertex-disjoint graphs.Definition 1.
TheQ-vertex corona of G1 and G2, denoted by G1⊙QG2, is the graph obtained from vertex disjoint Q(G1) and VG1 copies of G2 by joining the ith vertex of V(G1) to every vertex in the ith copy of G2.Definition 2.
TheQ-edge corona of G1 and G2, denoted by G1⊖QG2, is the graph obtained from vertex disjoint Q(G1) and IG1 copies of G2 by joining the ith vertex of I(G1) to every vertex in the ith copy of G2.Note that ifGi has ni vertices and mi edges for i=1,2, then G1⊙QG2 has n1+m1+n1n2 vertices and G1⊖QG2 has n1+m1+m1n2 vertices.LetPn and Cn denote a path and cycle with n vertices, respectively. From these definitions, Figure 1 shows the graphs C3⊙QP2 and C3⊖QP2.Figure 1
C
3
⊙
Q
P
2 and C3⊖QP2.Bu et al. investigated resistance distance in subdivision-vertex join and subdivision-edge join of graphs [4]. Liu et al. [5] gave the resistance distance and Kirchhoff index of R-vertex join and R-edge join of two graphs. Motivated by these works, in this paper we will work on two different composite networks: Q-vertex corona and Q-edge corona networks. In fact, we will follow the techniques used in [4] but in a slightly different method in order to obtain the effective resistances and the Kirchhoff indexes of Q-vertex corona and Q-edge corona networks in terms of the same parameters on the factors.


## 2. Preliminaries

In this section we list some lemmas as underlying but necessary preliminaries, which will be used in the proofs of our main results.Lemma 3 (see [7, 9]).
LetG be a connected graph. Then (1)ruvG=LG1uu+LG1vv-LG1uv-LG1vu=LG#uu+LG#vv-2LG#uv.Let1n denote the column vector of dimension n with all the entries equal to one. We will often use 1 to denote an all-ones column vector if the dimension can be read from the context.Lemma 4 (see [4]).
For any graph, one hasLG#1=0.Lemma 5 (see [17]).
Let(2)M=ABCDbe a nonsingular matrix. If A and D 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-1,where S=D-CA-1B.For a square matrixM, let tr(M) denote the trace of M.Lemma 6 (see [10]).
LetG be a connected graph on n vertices. Then (4)KfG=ntrLG1-1TLG11=ntrLG#.Lemma 7.
Let(5)L=ABBTDbe the Laplacian matrix of a connected graph. If D is nonsingular, then(6)X=H#-H#BD-1-D-1BTH#D-1+D-1BTH#BD-1is a symmetric {1}-inverse of L, where H=A-BD-1BT.Proof.
SinceH=A-BD-1BT is symmetric, H# exists and is symmetric. Since(7)L=IBD-10IH00DI0D-1BTI,we know that(8)X=I0-D-1BTIH#00D-1I-BD-10Iis a symmetric {1}-inverse of L.Remarks 1.
The above result is similar to Lemma2.8 in [10]; this is another form of Lemma 2.8, but in the process of computing the resistance distance of graphs G1⊙QG2 and G1⊖QG2, we use this formula to be more superior than Lemma 2.8 in [10].


## 3. Resistance Distance inQ-Vertex Coronae and Q-Edge Coronae of Two Graphs

We first give explicit resistance distance for the arbitrary two-vertex resistance distance inG1⊙QG2.Theorem 8.
LetG1 be an r1-regular graph on n1 vertices and m1 edges, and let G2 be an arbitrary graph on n2 vertices and m2 edges. Then the following holds:(i)
For anye,f∈E(G1), one has (9)refG1⊙QG2=r11+r1reflG1.(ii)
For anyu,v∈V(G2), one has(10)ruvG1⊙QG2=In1⊗LG2+In2-1n2+r1jn2×n2-1uu+In1⊗LG2+In2-1n2+r1jn2×n2-1vv-2In1⊗LG2+In2-1n2+r1jn2×n2-1uv.(iii)
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G1. For any u∈V(G1), f∈E(G1), one has(11)rufG1⊙QG2=1r1In1×n1+1r11+r1RLlG1#RTuu+r11+r1LlG1#ff-2r11+r1RLlG1#uf.(iv)
For anyu,v∈VG1(u≠v), let e1,e2,…,er (resp., f1,f2,…,fr) be r edges incident to u (resp., v) in G1, one has (12)ruvG1⊙QG2=2r1+1r1r1+1RLlG1#RTuu+1r1r1+1RLlG1#RTvv-2r1+1RLlG1#RTuv.(v)
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G1. For any u∈V(G1), v∈V(G2), one has (13)ruvG1⊙QG2=1r1+1r1r1+1RLlG1#RTuu+In1⊗LG2+In2-1n2+r1jn2×n2-1vv-2In1⊗LG2+In2-1n2+r1jn2×n2-1uv.(vi)
For anye∈E(G1), v∈V(G2), (14)revG1⊙QG2=r11+r1LlG1#ee+In1⊗LG2+In2-1n2+r1jn2×n2-1vv-21+r1RLlG1#ev.Proof.
LetB and R be the adjacency matrix of l(G1) and incidence matrix of G1, respectively. Then the Laplacian matrix of G1⊙QG2 is as follows:(15)LG1⊙QG2=2r1Im1-B-RT0m1×n1n2-Rr1+n2In1×n1-In1⊗1n2T0n1n2×m1-In1⊗1n2In1⊗LG2+In2.Let A=2r1Im1-B, B=-RT0m1×n1n2, BT=-R0n1n2×m1, and(16)D=r1+n2In1×n1-In1⊗1n2T-In1⊗1n2In1⊗LG2+In2.Note that RRT=DG1+AG1. Let R1=In1⊗(L(G2)+In2)-(-In1⊗1n2)((r1+n2)In1×n1)-1(-In1⊗1n2T)=In1⊗(LG2+In2-1/n2+r1jn2×n2)-1. By Lemma 5, we have(17)D-1=1r1In1×n11r1In1⊗1n2T1r1In1⊗1n2In1⊗LG2+In2-1n2+r1jn2×n2-1.
Now we are ready to calculate{1}-inverse of L(G1⊙QG2).
First we begin with the calculation aboutH.
LetQ=In1⊗(LG2+In2-1/n2+r1jn2×n2); then(18)
H
=
2
r
1
I
m
1
-
B
-
-
R
T
0
m
1
×
n
1
n
2
1
r
1
I
n
1
1
r
1
I
n
1
⊗
1
n
2
T
1
r
1
I
n
1
⊗
1
n
2
Q
-
1
-
R
0
n
1
n
2
×
m
1
=
2
r
1
I
m
1
-
B
-
-
1
r
R
T
-
1
r
1
R
T
I
n
1
⊗
1
n
2
T
-
R
0
n
1
n
2
×
m
1
=
2
r
1
I
m
1
-
B
-
1
r
1
2
I
m
1
+
B
=
1
+
r
1
r
1
L
l
G
1
.By Lemma 7, we have H#=r1/1+r1Ll(G1)#.
Next according to Lemma7, we calculate -H#BD-1 and -D-1BTH#:(19)
-
H
#
B
D
-
1
=
-
r
1
1
+
r
1
L
l
G
1
#
-
R
T
0
m
1
×
n
1
n
2
1
r
1
I
n
1
1
r
1
I
n
1
⊗
1
n
2
T
1
r
1
I
n
1
⊗
1
n
2
Q
-
1
=
-
r
1
1
+
r
1
L
l
G
1
#
-
1
r
1
R
T
-
1
r
1
R
T
I
n
1
⊗
1
n
2
T
=
1
1
+
r
1
L
l
G
1
#
R
T
L
l
G
1
#
R
T
I
n
1
⊗
1
n
2
T
,
-
D
-
1
B
T
H
#
=
-
1
r
1
I
n
1
1
r
1
I
n
1
⊗
1
n
2
T
1
r
1
I
n
1
⊗
1
n
2
Q
-
1
-
R
0
n
1
n
2
×
m
1
r
1
1
+
r
1
L
l
G
1
#
=
1
r
1
R
1
r
1
I
n
1
⊗
1
n
2
R
r
1
1
+
r
1
L
l
G
1
#
=
1
1
+
r
1
R
L
l
G
1
#
I
n
1
⊗
1
n
2
R
L
l
G
1
#
.We are ready to compute D-1BTH#BD-1.
LetK=In1⊗1n2, Q=In1⊗(LG2+In2-1/n2+r1jn2×n2)-1; then(20)
D
-
1
B
T
H
#
B
D
-
1
=
-
1
1
+
r
1
R
L
l
G
1
#
K
R
L
l
G
1
#
-
R
T
0
m
1
×
n
1
n
2
1
r
1
I
n
1
×
n
1
1
r
1
K
T
1
r
1
K
Q
-
1
=
-
1
1
+
r
1
R
L
l
G
1
#
K
R
L
l
G
1
#
-
1
r
1
R
T
-
1
r
1
R
T
K
T
=
1
r
1
1
+
r
1
R
L
l
G
1
#
R
T
1
r
1
1
+
r
1
R
L
l
G
1
#
R
T
K
T
1
r
1
1
+
r
1
K
R
L
l
G
1
#
R
T
1
r
1
1
+
r
1
K
R
L
l
G
1
#
R
T
K
T
.Based on Lemmas 5 and 7, the following matrix(21)
N
=
r
1
1
+
r
1
L
l
G
1
#
1
1
+
r
1
L
l
G
1
#
R
T
1
1
+
r
1
L
l
G
1
#
R
T
K
T
1
1
+
r
1
R
L
l
G
1
#
1
r
1
I
n
1
×
n
1
+
1
r
1
1
+
r
1
R
L
l
G
1
#
R
T
1
r
1
1
+
r
1
R
L
l
G
1
#
R
T
K
T
+
1
r
1
K
T
1
1
+
r
1
K
R
L
l
G
1
#
1
r
1
K
+
1
r
1
1
+
r
1
K
R
L
l
G
1
#
R
T
Q
-
1
+
1
r
1
1
+
r
1
K
R
L
l
G
1
#
R
T
K
Tis a symmetric {1}-inverse of L(G1⊙QG2), where K=In1⊗1n2 and Q=In1⊗(LG2+In2-1/n2+r1jn2×n2).
For anye,f∈E(G1), by Lemma 3 and (21), we have (22)refG1⊙QG2=r11+r1reflG1.
For anyu,v∈V(G2), by Lemma 3 and (21), we have (23)ruvG1⊙QG2=In1⊗LG2+In2-1n2+r1jn2×n2-1uu+In1⊗LG2+In2-1n2+r1jn2×n2-1vv-2In1⊗LG2+In2-1n2+r1jn2×n2-1uv.
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G1. For any u∈V(G1), f∈E(G1), by Lemma 3 and (21), we have (24)rufG1⊙QG2=1r1In1×n1+1r11+r1RLlG1#RTuu+r11+r1LlG1#ff-21+r1RLlG1#uf.
For anyu,v∈VG1(u≠v), let e1,e2,…,er (resp., f1,f2,…,fr) be r edges incident to u (resp., v) in G1. By Lemma 3 and (21), we have (25)ruvG1⊙QG2=2r1+1r1r1+1RLlG1#RTuu+1r1r1+1RLlG1#RTvv-2r1r1+1RLlG1#RTuv.
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G1. For any u∈V(G1), v∈V(G2), by Lemma 3 and (21), we have (26)ruvG1⊙QG2=1r1+1r1r1+1RLlG1#RTuu+In1⊗LG2+In2-1n2+r1jn2×n2-1vv-2In1⊗LG2+In2-1n2+r1jn2×n2-1uv.
For anye∈E(G1), v∈V(G2), by Lemma 3 and (21), we have (27)revG1⊙QG2=r11+r1LlG1#ee+In1⊗LG2+In2-1n2+r1jn2×n2-1vv-21+r1RLlG1#ev.Next it will give the formulae for resistance distance of graphG1⊖QG2 when G1 is a regular graph as follows.Theorem 9.
LetG1 be an r1-regular graph with n1 vertices, and let G2 be an arbitrary graph with n2 vertices. Then the following holds:(i)
For anye,f∈E(G1), one has (28)refG1⊖QG2=r11+r1reflG1.(ii)
For anyu,v∈V(G2), one has (29)ruvG1⊖QG2=Im1⊗LG2+In2-1uu+Im1⊗LG2+In2-1vv-2Im1⊗LG2+In2-1uv.(iii)
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G. For any u∈V(G1),f∈E(G1), one has (30)rufG1⊖QG2=1r1In1×n1+1r11+r1RLlG1#RTuu+r11+r1LlG1#ff-21+r1RLlG1#uf.(iv)
For anyu,v∈VG1 (u≠v), let e1,e2,…,er (resp., f1,f2,…,fr) be r edges incident to u (resp., v) in G1; one has(31)ruvG1⊖QG2=2r1+1r1r1+1RLlG1#RTuu+1r1r1+1RLlG1#RTvv-2r1r1+1RLlG1#RTuv.(v)
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G1. For any u∈V(G1), v∈V(G2), one has (32)ruvG1⊖QG2=1r1+1r1r1+1RLlG1#RTuu+Im1⊗LG2+In2-1vv-2Im1⊗LG2+In2-1uv.(vi)
For anye∈E(G1), v∈V(G2), one has (33)revG1⊖QG2=r11+r1LlG1#ee+Im1⊗LG2+In2-1vv-21+r1RLlG1#ev.Proof.
LetB and R be the adjacency matrix of l(G1) and incidence matrix of G1, respectively. Then the Laplacian matrix of G1⊖QG2 is as follows:(34)LG1⊖QG2=2r1+n2Im1-B-RT-Im1⊗1n2T-Rr1In10n1×n2m1-Im1⊗1n20n2m1×n1Im1⊗LG2+In2.Now we are ready to calculate a {1}-inverse of L(G1⊖QG2).
First we are ready to calculateH#.
LetM=Im1⊗1n2, P=Im1⊗(L(G2)+In2), then(35)H=2r1+n2Im1-B--RT-MTr1In10n1×n2m10n2m1×n1P-1-R-M=2r1+n2Im1-B--1r1RT-MTP-1-R-M=2r1+n2Im1-B-1r1RTR-n2Im1=1+r1r1LlG1.By Lemma 7, we have H#=r1/1+r1Ll(G1)#.
Next we compute-H#BD-1 and -D-1BTH#:(36)
-
H
#
B
D
-
1
=
-
r
1
1
+
r
1
L
l
G
1
#
-
R
T
-
I
m
1
⊗
1
n
2
T
1
r
1
I
n
1
0
n
1
×
n
2
m
1
0
n
2
m
1
×
n
1
I
m
1
⊗
L
G
2
+
I
n
2
-
1
=
-
r
1
1
+
r
1
L
l
G
1
#
-
1
r
1
R
T
-
I
m
1
⊗
1
n
2
T
=
1
r
1
+
1
L
l
G
1
#
R
T
r
1
r
1
+
1
L
l
G
1
#
I
m
1
⊗
1
n
2
T
,
-
D
-
1
B
T
H
#
=
-
1
r
1
I
n
1
0
n
1
×
n
2
m
1
0
n
2
m
1
×
n
1
I
m
1
⊗
L
G
2
+
I
n
2
-
1
-
R
-
I
m
1
⊗
1
n
2
r
1
1
+
r
1
L
l
G
1
#
=
r
1
1
+
r
1
1
r
1
R
I
m
1
⊗
1
n
2
L
l
G
1
#
=
1
r
1
+
1
R
L
l
G
1
#
r
1
r
1
+
1
I
m
1
⊗
1
n
2
L
l
G
1
#
.We are ready to compute D-1BTH#BD-1:(37)
D
-
1
B
T
H
#
B
D
-
1
=
-
1
r
1
+
1
R
L
l
G
1
#
r
1
r
1
+
1
M
L
l
G
1
#
-
R
T
-
M
T
1
r
1
I
n
1
0
n
1
×
n
2
m
1
0
n
2
m
1
×
n
1
P
-
1
=
-
1
r
1
+
1
R
L
l
G
1
#
r
1
r
1
+
1
M
L
l
G
1
#
-
1
r
1
R
T
-
M
T
P
-
1
=
1
r
1
r
1
+
1
R
L
l
G
1
#
R
T
1
r
1
+
1
R
L
l
G
1
#
M
T
1
r
1
+
1
M
L
l
G
1
#
R
T
r
1
r
1
+
1
M
L
l
G
1
#
M
T
.Based on Lemmas 5 and 7, the following matrix(38)
N
=
r
1
1
+
r
1
L
l
G
1
#
1
r
1
+
1
L
l
G
1
#
R
T
r
1
r
1
+
1
L
l
G
1
#
M
T
1
1
+
r
1
R
L
l
G
1
#
1
r
1
I
n
1
+
1
r
1
r
1
+
1
R
L
l
G
1
#
R
T
1
r
1
+
1
R
L
l
G
1
#
M
T
1
1
+
r
1
M
L
l
G
1
#
1
r
1
+
1
M
L
l
G
1
#
R
T
P
-
1
+
r
1
r
1
+
1
M
L
l
G
1
#
M
Tis a symmetric {1}-inverse of L(G1⊖QG2), where M=Im1⊗1n2 and P=Im1⊗(L(G2)+In2).
For anye,f∈E(G1), by Lemma 3 and (38), we have (39)refG1⊖QG2=r11+r1reflG1.
For anyu,v∈V(G2), by Lemma 3 and (38), we have (40)ruvG1⊖QG2=Im1⊗LG2+In2-1uu+Im1⊗LG2+In2-1vv-2Im1⊗LG2+In2-1uv.
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G. For any u∈V(G1),f∈E(G1), by Lemma 3 and (38), we have (41)rufG1⊖QG2=1r1In1×n1+1r11+r1RLlG1#RTuu+r11+r1LlG1#ff-21+r1RLlG1#uf.
For anyu,v∈VG1  (u≠v), let e1,e2,…,er (resp., f1,f2,…,fr) be r edges incident to u (resp., v) in G1. By Lemma 3 and (38), we have (42)ruvG1⊖QG2=2r1+1r1r1+1RLlG1#RTuu+1r1r1+1RLlG1#RTvv-2r1r1+1RLlG1#RTuv.
For anyu∈V(G1), let e1,e2,…,er be r edges incident to u in G1. For any u∈V(G1), v∈V(G2), by Lemma 3 and (38), we have (43)ruvG1⊖QG2=1r1+1r1r1+1RLlG1#RTuu+Im1⊗LG2+In2-1vv-2Im1⊗LG2+In2-1uv.
For anye∈E(G1), v∈V(G2), by Lemma 3 and (38), we have (44)revG1⊖QG2=r11+r1LlG1#ee+Im1⊗LG2+In2-1vv-21+r1RLlG1#ev.


## 4. Kirchhoff Index inQ-Vertex Corona and Q-Edge Corona of Two Graphs

Theorem 10.
LetG1 be an r1-regular graph on n1 vertices and m1 edges, and let G2 be an arbitrary graph on n2 vertices and m2 edges. Then the following holds: (45)KfG1⊙QG2=n1+m1+n1n2r11+r1trLlG1#+n1r1In1+1r11+r1trRLlG1#RT+n1∑i=1n21μiG2+1+1r1r1+1trIn1⊗1n2RLlG1#RTIn1⊗1n2T-n1r1-3n1n2.Proof.
LetLG1⊙QG2(1) be the symmetric {1}-inverse of LG1⊙QG2. Then (46)trLG1⊙QG21=r11+r1trLlG1#+tr1r1In1+1r11+r1RLlG1#RT+trIn1⊗LG2+In2-1n2+r1jn2×n2-1+1r1r1+1trIn1⊗1n2RLlG1#RTIn1⊗1n2T.Note that the eigenvalues of (LG2+In2-1/n2+r1jn2×n2) are μ1(G2)+1,μ2(G2)+1,…,μn2(G2)+1. Then (47)trIn1⊗LG2+In2-1n2+r1jn2×n2=n1∑i=1n2μiG2+1-1=n1∑i=1n21μiG2+1.So(48)trLG1⊙QG21=r11+r1trLlG1#+n1r1In1+1r11+r1trRLlG1#RT+n1∑i=1n21μiG2+1+1r1r1+1trIn1⊗1n2RLlG1#RTIn1⊗1n2T.
Next, we calculate1T(LG1⊙QG2(1))1. Since, by Lemma 4, LG#1=0, then(49)1TLG1⊙QG211=1T1r1In1+1r11+r1RLlG1#RT1+1r11+r11TRLlG1#RTIn1⊗1n2T+1r1In1⊗1n2T1+1T1r1In1⊗1n2+1r11+r1In1⊗1n2RLlG1#RT1+1TQ-1+1r11+r1In1⊗1n2RLlG1#RTIn1⊗1n2T1,where Q=LG2+In2-1/n2+r1jn2×n2. Since 1TR=RT1=2·1, then(50)1TRLlG1#RT1=1TRLlG1#RTIm1⊗1n2T1=1TIn1⊗1n2TRLlG1#RT1=1TIn1⊗1n2RLlG1#RTIn1⊗1n2T1=0.
LetT=1n1n2T(In1⊗(LG2+In2-1/n2+r1jn2×n2)-1)1n2n1; then(51)T=1n2T1n2T⋯1n2TQ-1Q-1⋱Q-11n21n2⋮1n2=1n2TLG2+In2-1n2+r1jn2×n2-1⋯1n2TLG2+In2-1n2+r1jn2×n2-11n21n2⋮1n2=n11n2TLG2+In2-1n2+r1jn2×n2-11n2=n1n2.So(52)1TLG1⊙QG211=n1r1+3n1n2.Lemma 6 implies that (53)KfLG1⊙QG21=n1+m1+n1n2trLG1#-1TLG1⊙QG211.Then plugging tr(LG1⊙QG2(1)) and 1T(LG1⊙QG2(1))1 into the equation above, we obtain the required result.Theorem 11.
LetG1 be an r1-regular graph with n1 vertices, and let G2 be an arbitrary graph with n2 vertices. Then(54)KfG1⊖QG2=n1+m1+m1n2r11+r1trLlG1#+n2r1+1r1r1+1trRLG1#RT+m1∑i=1n21μiG2+2+11+r1trIm1⊗1n2LlG1#Im1⊗1n2T-n1r1-n1n2.Proof.
The proof is similar to those of Theorem10, omitted.



---

*Source: 4682527-2016-02-08.xml*