# Resistance Distance in Tensor and Strong Product of Path or Cycle Graphs Based on the Generalized Inverse Approach

Authors: Muhammad Shoaib Sardar; Xiang-Feng Pan; Dalal Alrowaili; Imran Siddique
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Graph product plays a key role in many applications of graph theory because many large graphs can be constructed from small graphs by using graph products. Here, we discuss two of the most frequent graph-theoretical products. LetG1 and G2 be two graphs. The Cartesian product G1□G2 of any two graphs G1 and G2 is a graph whose vertex set is VG1□G2=VG1×VG2 and a1,a2b1,b2∈EG1□G2 if either a1=b1 and a2b2∈EG2 or a1b1∈EG1 and a2=b2. The tensor product G1×G2 of G1 and G2 is a graph whose vertex set is VG1×G2=VG1×VG2 and a1,a2b1,b2∈EG1×G2 if a1b1∈EG1 and a2b2∈EG2. The strong product G1⊠G2 of any two graphs G1 and G2 is a graph whose vertex set is defined by VG1⊠G2=VG1×VG2 and edge set is defined by EG1⊠G2=EG1□G2∪EG1×G2. The resistance distance among two vertices u and v of a graph G is determined as the effective resistance among the two vertices when a unit resistor replaces each edge of G. Let Pn and Cn denote a path and a cycle of order n, respectively. In this paper, the generalized inverse of Laplacian matrix for the graphs Pn1×Cn2 and Pn1⊠Pn2 was procured, based on which the resistance distances of any two vertices in Pn1×Cn2 and Pn1⊠Pn2 can be acquired. Also, we give some examples as applications, which elucidated the effectiveness of the suggested method.


---

## Body

## 1. Introduction

Graph products [1] became an interesting area of research, and different types of products have been worked out in graph theory and other fields. The Cartesian product G1□G2 of any two graphs G1 and G2 is a graph whose vertex set is VG1×VG2 and two vertices a1,a2 and b1,b2 are adjacent in G1□G2 if and only if either a1=b1 and a2 is adjacent to b2 in G2, or a2=b2 and a1 is adjacent to b1 in G1. The tensor product G1×G2 of G1 and G2 is a graph whose vertex set is the Cartesian product of VG1×VG2 and distinct vertices a1,a2 and b1,b2 are adjacent in G1×G2 if a1 is adjacent to b1 and a2 is adjacent to b2. The strong product G1⊠G2 of graph G1 and G2 is a graph whose vertex set is VG1□G2 and distinct vertices a1,a2 and b1,b2 are adjacent in G1⊠G2 if either a1=b1 and a2 is adjacent to b2, or a2=b2 and a1 is adjacent to b1, or a1 is adjacent to b1 and a2 is adjacent to b2. It is the union of Cartesian product and tensor product. Sabidussi first proposed it in 1960 [2]. Let Pn and Cn be the path and the cycle graphs of order n, respectively. From the definition of tensor and strong product of graphs, the graphs P4×C4 and P4⊠P4 are depicted in Figure 1. The graph depicted in Figure 1(b) is also called a King’s graph which is a strong product of two path graphs.Figure 1
(a)P4×C4. (b)P4⊠P4.
(a)(b)The resistance distance is a function of the distance in graphs, as suggested by Klein and Randic´ [3]. The resistance distance between any two vertices of a simple connected graph, G, is equal to the resistance between two equivalent points on an electrical network, constructed in such a way as G, of each of the edge to replace a load resistance of 1 ohm. It is symbolized by rij, where i,j∈V. The computation of resistance is relevant to a wide range of applications ranging from random walks [4], opinion formation [5], classical transport in disordered media [6], robustness of coupled oscillators network [7–9], first-passage processes [10], identifying the influential spreader node in a network [11], lattice Greens functions [12, 13], and resistance distance [3, 14] to graph theory [13, 15, 16]. At present, the resistance distance is a very suitable tool and internal graphic measurement to express the wave-like or fluid-like communication between two vertices [17]. It is also well studied in chemical and mathematical literature [3, 18–23].Many kinds of formulae were attained for calculating the resistance distance, i.e., probabilistic formulae [4, 24], algebraic formulae [25–31], combinatorial formula [28], and so forth. Resistance distances have been procured for certain types of graphs, i.e., wheels and fans [18], cyclic graphs [32], some fullerene graphs [33], Cayley graphs [34], regular graphs [35, 36], pseudodistance regular graphs [37], and so forth. In recent years, the resistance distance of some graphic operations has been calculated (see [20, 38–41]).In the present paper, we investigated the generalized inverse of Laplacian matrix for the graphsPn1×Cn2 and Pn1⊠Pn2, based on which two-vertex resistances in Pn1×Cn2 and Pn1⊠Pn2 can be procured.We ordered the paper in the following way. Section2 covers some preliminary knowledge, i.e., basic definitions and necessary lemmas. In Section 3, we prove our main results, i.e., the generalized inverse of Laplacian matrix for tensor and strong product networks Pn1×Pn2 and Pn1⊠Pn2. In Section 4, as an application, we present a few examples. The final remarks are given in Section 5.


## 2. Preliminaries and Lemmas

LetG be a simple graph, and the vertex and edge sets of G are symbolized by VG=v1,v2,…,vn and EG=e1,e2,…,em, respectively. The adjacency matrix AG of a graph G is an n×n matrix, whose element auv is one when there is an edge among vertex u and vertex v and zero when there is no edge between vertex u and vertex v. Let DG be diagonal matrix with diagonal entries dGv1,dGv2,…,dGvn. For a graph G, let LG=DG−AG be a Laplacian matrix of order n×n. The incidence matrix BG of a graph G is an n×m matrix, where n and m are numbers of vertices and edges, respectively, such that Bij is 1 if the vertex vi and edge ej are incident and 0 otherwise. The identity matrix In is an n×n square matrix with 1s on main diagonal and 0s elsewhere.LetM=muvi×j and N=nuvl×m be the two matrices. The Kronecker product M⊗N is the il×jm matrix acquired from M by replacing each element muv by muvN [42]. Let M1,1G be the matrix acquired by removing the 1st row and 1st column of a matrix MG of a graph G, and matrix B1G is equal to the 1st row of an incidence matrix BG of a graph G. For example, considering a path graph P3, the Laplacian matrix LP3 is 1−10−12−10−11; then, L1,1P3=2−1−11. The incidence matrix BP3 is 101101; then, B1P3=10.LetM be a square matrix. A matrix Z is called a 1-inverse of M if it satisfies MZM=M. 1-inverse of M is represented as M1. A matrix Z is a group inverse of a matrix M if it meets the following conditions [38]:(i)
MZM=M(ii)
ZMZ=Z(iii)
ZM=MZLetM# symbolize a group inverse of M. 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 [38].The following lemma is used for computing the resistance distance.Lemma 1 (see [38]).
LetL be a Laplacian matrix of a simple graph G with vertex set 1,2,…,n. Then,(1)rxy=Lxx#+Lyy#−2Lxy#.Lemma 2 (see [38]).
For a nonsingular matrixM=QNRP, if Q and P are nonsingular and S=P−RQ−1N, then(2)M−1=Q−1+Q−1NS−1RQ−1−Q−1NS−1−S−1RA−1S−1is the Schur complement of Q in M.C. Bu, in [38], stated the following expression.Lemma 3 (see [38]).
LetL=L1L2L2TL3 be a Laplacian matrix of a graph G and suppose each a column vector of L2 is a zero vector or −1; then, the following matrix is a symmetric 1-inverse of L:(3)X=L1−100S#,where S=L3−L2TL1−1L2.The following expression, similar to Lemma3, also holds for the Laplacian matrix of a simple graph. For more details, see [22, 39, 43].Lemma 4.
If the Laplacian matrix of a simple graphG is partitioned as L=L1L2L2TL3 and L1 is nonsingular, then the following matrix is a symmetric 1-inverse of L:(4)X=L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where S=L3−L2TL1−1L2.


## 3. Main Results

### 3.1. The Laplacian Generalized Inverse for GraphPn1×Cn1

Theorem 1.
LetG1 and G2 be a path graph and a cycle graph with vertices n1 and n2, respectively. Then, the symmetric 1-inverse of LG1×G1 is(5)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(6)L1=DG2,L2=−B1G1⊗AG2,L3=2D1,1G1⊗In2−A1,1G1⊗AG2,S=L3−B1G1TB1G1⊗AG2DG2−1AG2.Proof.
LetVG1=a1,a2,…,an1 and VG2=b1,b2,…,bn2. Then,(7)a1,a2,…,an1×b1,b2,…,bn2is a partition of VG1×G2, where a1,b1 and a2,b2 are adjacent whenever a1,a2 is an edge in G1 and b1,b2 is an edge in G2. In G1×G2, 2n2 vertices are of degree 2 and n2n1−2 vertices are of degree 4. Label the vertices of G1×G2 like in Figure 1(a). According to partition (7), the Laplacian matrix of G1×G2 can be written as(8)DG2−B1G1⊗AG2−B1G1T⊗AG22D1,1G1⊗In2−A1,1G1⊗AG2.
We start with the calculation ofS. For simplicity, let(9)L1=DG2,L2=−B1G1⊗AG2,L2T=−B1G1T⊗AG2,L3=2D1,1G1⊗In2−A1,1G1⊗AG2.
Due to Lemma4, we have(10)S=2D1,1G1⊗In2−A1,1G1⊗AG2−−B1G1⊗AG2TDG2−1−B1G1⊗AG2=L3−B1G1T⊗AG2DG2−1B1G1⊗AG2=L3−B1G1TB1G1⊗AG2DG2−1AG2.
By using Lemma4, the symmetric 1-inverse of LG1×G2 is(11)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(12)L1=DG2,L2=−B1G1⊗AG2,L3=2D1,1G1⊗In2−A1,1G1⊗AG2,S=L3−B1G1TB1G1⊗AG2DG2−1AG2.


### 3.2. The Laplacian Generalized Inverse for GraphPn1⊠Pn2

Theorem 2.
LetG1 and G2 be two paths with n1 and n2 vertices, respectively, and let(13)D=50…008⋮⋱8558⋱8535⋱503n1−1n2×n1−1n2.Then, the symmetric1-inverse of LG1×G2 is(14)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(15)L1=2DG2+In2−AG2,L2=−B1G1⊗AG2+In2,L3=D−In1−1⊗AG2+A1,1G1⊗AG2+In2,S=L3−B1G1TB1G1⊗AG2+In2L1−1AG2+In2.Proof.
LetVG1=a1,a2,…,an1 and VG2=b1,b2,…,bn2. Then,(16)VG1⊠G2=a,b|a∈VG1,b∈VG2and EG1⊠G2=EG1□G2∪EG1×G2. The degree of vertices of G1⊠G2 is(17)dG1⊠G2a,b=dG1a+dG2b+dG1a⋅dG2b,a,b∈EG1⊠G2.
Label the vertices ofG1⊠G2 like in Figure 1(b). According to partition (16), the Laplacian matrix of G1⊠G2 can be written as(18)2DG2+In2−AG2−B1G1⊗AG2+In2−B1G1T⊗AG2+In2D−In1−1⊗AG2+A1,1G1⊗AG2+In2.
We start with the calculation ofS. For simplicity, let(19)L1=2DG2+In2−AG2,L2=−B1G1⊗AG2+In2,L2T=−B1G1T⊗AG2+In2,L3=D−In1−1⊗AG2+A1,1G1⊗AG2+In2.
Due to Lemma4, we have(20)S=L3−B1G1T⊗AG2+In2L1−1B1G1⊗AG2+In2=L3−B1G1TB1G1⊗AG2+In2L1−1AG2+In2.
By using Lemma4, the symmetric 1-inverse of LG1⊠G2 is(21)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(22)L1=2DG2+In2−AG2,L2=−B1G1⊗AG2+In2,L3=D−In1−1⊗AG2+A1,1G1⊗AG2+In2,S=L3−B1G1TB1G1⊗AG2+In2L1−1AG2+In2.


## 3.1. The Laplacian Generalized Inverse for GraphPn1×Cn1

Theorem 1.
LetG1 and G2 be a path graph and a cycle graph with vertices n1 and n2, respectively. Then, the symmetric 1-inverse of LG1×G1 is(5)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(6)L1=DG2,L2=−B1G1⊗AG2,L3=2D1,1G1⊗In2−A1,1G1⊗AG2,S=L3−B1G1TB1G1⊗AG2DG2−1AG2.Proof.
LetVG1=a1,a2,…,an1 and VG2=b1,b2,…,bn2. Then,(7)a1,a2,…,an1×b1,b2,…,bn2is a partition of VG1×G2, where a1,b1 and a2,b2 are adjacent whenever a1,a2 is an edge in G1 and b1,b2 is an edge in G2. In G1×G2, 2n2 vertices are of degree 2 and n2n1−2 vertices are of degree 4. Label the vertices of G1×G2 like in Figure 1(a). According to partition (7), the Laplacian matrix of G1×G2 can be written as(8)DG2−B1G1⊗AG2−B1G1T⊗AG22D1,1G1⊗In2−A1,1G1⊗AG2.
We start with the calculation ofS. For simplicity, let(9)L1=DG2,L2=−B1G1⊗AG2,L2T=−B1G1T⊗AG2,L3=2D1,1G1⊗In2−A1,1G1⊗AG2.
Due to Lemma4, we have(10)S=2D1,1G1⊗In2−A1,1G1⊗AG2−−B1G1⊗AG2TDG2−1−B1G1⊗AG2=L3−B1G1T⊗AG2DG2−1B1G1⊗AG2=L3−B1G1TB1G1⊗AG2DG2−1AG2.
By using Lemma4, the symmetric 1-inverse of LG1×G2 is(11)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(12)L1=DG2,L2=−B1G1⊗AG2,L3=2D1,1G1⊗In2−A1,1G1⊗AG2,S=L3−B1G1TB1G1⊗AG2DG2−1AG2.


## 3.2. The Laplacian Generalized Inverse for GraphPn1⊠Pn2

Theorem 2.
LetG1 and G2 be two paths with n1 and n2 vertices, respectively, and let(13)D=50…008⋮⋱8558⋱8535⋱503n1−1n2×n1−1n2.Then, the symmetric1-inverse of LG1×G2 is(14)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(15)L1=2DG2+In2−AG2,L2=−B1G1⊗AG2+In2,L3=D−In1−1⊗AG2+A1,1G1⊗AG2+In2,S=L3−B1G1TB1G1⊗AG2+In2L1−1AG2+In2.Proof.
LetVG1=a1,a2,…,an1 and VG2=b1,b2,…,bn2. Then,(16)VG1⊠G2=a,b|a∈VG1,b∈VG2and EG1⊠G2=EG1□G2∪EG1×G2. The degree of vertices of G1⊠G2 is(17)dG1⊠G2a,b=dG1a+dG2b+dG1a⋅dG2b,a,b∈EG1⊠G2.
Label the vertices ofG1⊠G2 like in Figure 1(b). According to partition (16), the Laplacian matrix of G1⊠G2 can be written as(18)2DG2+In2−AG2−B1G1⊗AG2+In2−B1G1T⊗AG2+In2D−In1−1⊗AG2+A1,1G1⊗AG2+In2.
We start with the calculation ofS. For simplicity, let(19)L1=2DG2+In2−AG2,L2=−B1G1⊗AG2+In2,L2T=−B1G1T⊗AG2+In2,L3=D−In1−1⊗AG2+A1,1G1⊗AG2+In2.
Due to Lemma4, we have(20)S=L3−B1G1T⊗AG2+In2L1−1B1G1⊗AG2+In2=L3−B1G1TB1G1⊗AG2+In2L1−1AG2+In2.
By using Lemma4, the symmetric 1-inverse of LG1⊠G2 is(21)L1−1+L1−1L2S#L2TL1−1−L1−1L2S#−S#L2TL1−1S#,where(22)L1=2DG2+In2−AG2,L2=−B1G1⊗AG2+In2,L3=D−In1−1⊗AG2+A1,1G1⊗AG2+In2,S=L3−B1G1TB1G1⊗AG2+In2L1−1AG2+In2.


## 4. Examples to Summarize the Main Results

Here, we discuss few examples to show that two-vertex resistances in graphsPn1×Cn2 and Pn1×Pn2 can be procured by the proposed method.Example 1.
The resistance distance matrix for the graphP3×C3 (see Figure 2(a)).
The Laplacian matrix ofP3×C3 is(23)DC3−B1P3⊗AC3−B1P3T⊗AC32D1,1P3⊗I3−A1,1P3⊗AC3.
From Theorem1, we obtain(24)L#P3×C3=4372172172−572772772172−572−5721724372172772−572772−572172−5721721724372772772−572−572−572172−5727727721972−572−572−1172172172772−572772−5721972−572172−1172172772772−572−572−5721972172172−1172172−572−572−11721721723172−1172−1172−572172−572172−1172172−11723172−1172−572−572172172172−1172−1172−11723172.
By using Lemma1 and L#P3×C3, the resistance distance matrix of P3×C3 is(25)R#P3×C3=076761232317676760762312376176767602323176761123230232312323231232302323123232312323023231176761232307676761762312376076767612323176760,where rij denotes the two-vertex resistance between vertices i and j.Figure 2
(a)P3×C3. (b) P3⊠P3.
(a)(b)Example 2.
The resistance distance matrix for the graphP3⊠P3 (see Figure 2(b)).
The Laplacian matrix ofP3⊠P3 is(26)2DP3+I3−AP3−B1P3×AP3+I3−B1P3T×AP3+I3D−I2⊗AP3+A1,1P3⊗AP3+I3,where D=500000080000005000000300000050000003.
Based on Theorem2, we obtain that(27)L#P3⊠P3=72817795346872143322732762124699−253276−43716380−136−857163805346812546853468174681746817468−19468−136−19468721433534687281779−25327621246992273276−85716380−136−43716380227327617468−2532763461931−253276−13252−253276−136−27732762124699174682124699−2532761171097−253276−912861−136−912861−253276174682273276−13252−2532765873276−2773276−136−253276−43716380−19468−85716380−253276−912861−27732765112001−136−2792693−136−136−136−136−136−136−136536−136−85716380−19468−43716380−2773276−912861−253276−2792693−1365112001.
By using Lemma1 and L#P3⊠P3, the resistance distance matrix of P3⊠P3(28)R#P3⊠P3=06141365283961413658319582413652839824136510136141365061413653491137455349182413656138241365283961413650824136583195614136510138241365283961413653491824136501374556136141365349182413658319513745583195137455013745583195137455831958241365349161413656131374550824136534916141365283982413651013614136583195824136506141365283982413656138241365349113745534916141365061413651013824136528398241365831956141365283961413650,where rij denotes the two-vertex resistance between vertices i and j.


## 5. Conclusion

In this paper, we investigated the resistance distance in the tensor product of a path and a cycle as well as the strong product of two paths. First, we obtained the Laplacian matrix of these two kinds of product graphs. After calculation, we acquire the generalized inverse representations of the Laplacian matrices, and then, applying the generalized inverse theory of block matrices, we obtained the two-vertex resistances. Finally, we applied the above method to compute the resistance distance in graphsP3×C3 and P3⊠P3. We obtained the resistance distance between two pair of vertices in tensor and strong product of two classes of graphs. However, the resistance distance for some other graph products has not been solved yet. We recommend the readers to compute the resistance distance for other classes of graphs by using different graph products, i.e., zig zag product, modular product, co-normal product and lexicographical product.



---

*Source: 1712685-2021-08-09.xml*