# The (Multiplicative Degree-) Kirchhoff Index of Graphs Derived from the Cartesian Product ofSn and K2

Authors: Jia-Bao Liu; Xin-Bei Peng; Jiao-Jiao Gu; Wenshui Lin
Journal: Journal of Mathematics
 (2022)

---

## Abstract

It is well known that many topological indices have widespread use in lots of fields about scientific research, and the Kirchhoff index plays a major role in many different sectors over the years. Recently, Li et al. (Appl. Math. Comput. 382 (2020) 125335) proposed the problem of determining the Kirchhoff index and multiplicative degree-Kirchhoff index of graphs derived fromSn×K2, the Cartesian product of the star Sn, and the complete graph K2. In the present study, we completely solve this problem, that is, the explicit closed-form formulae of the Kirchhoff index, multiplicative degree-Kirchhoff index, and number of spanning trees are obtained for some graphs derived from Sn×K2.


---

## Body

## 1. Introduction

In this study, we suppose thatG=V,E is a nontrivial simple and connected graph, where V=v1,v2,…,vn and E are the vertex set and edge set of G, respectively. Let AG=aijn×n be the adjacency matrix, and DG=diagd1,d2,…,dn the degree matrix, where di is the degree of vertex vi. Then, LG=DG−AG is termed as the Laplacian matrix, and ℒG=DG−1/2LGDG−1/2 the normalized Laplacian matrix of graph G. It is easily seen that(1)ℒGij=1,ifi=j;−1didj,ifi≠jandvivj∈E;0,otherwise.Let0=μ1<μ2≤⋯≤μn be the eigenvalues of LG and 0=ν1<ν2≤⋯≤νn the eigenvalues of ℒG. The sets SpLG=μ1,μ2,…,μn and SpℒG=ν1,ν2,…,νn are called the Laplacian spectrum and normalized Laplacian spectrum of G, respectively.For two verticesvi and vj, the distance between them written as dij is the length of the shortest path linking them. The Wiener index [1] and Gutman index [2] of G are defined as WG=∑i<jdij and GutG=∑i<jdidjdij. For these two famous topological indices, one can refer to [3–10] and the references therein.If regard each edge inEG as an unit resistor, then for two vertices vi and vj, rij is represented as the effective resistance between them [11]. In the field of chemistry, resistance distance has been studied extensively and many profound results have been obtained. One of the most famous results is the Kirchhoff index, which is used to characterize the structure of a compound. The Kirchhoff index of G is written as KfG=∑i<jrij. It is derived from molecular diagrams and is also a form used to numerically characterize molecules. Hitherto, the Kirchhoff index has been widely applied to mathematic, chemistry, physics, and so on. Later, the following relation between KfG and SpLG was established by Zhu et al. [12] and Gutman and Mohar [13] independently.Lemma 1 (See [12, 13]).
LetG be a simple graph of order n≥2. Then,(2)KfG=∑i=2n1μi.Similarly, Chen and Zhang [14] defined the multiplicative degree-Kirchhoff index of G as Kf∗G=∑i<jdidjrij. Moreover, the following relation between Kf∗G and SpℒG was confirmed.Lemma 2 (See [14]).
LetG be a simple connected graph of order n≥2 and size m. Then,(3)Kf∗G=2m∑i=2n1νi.Nowadays, the (multiplicative degree-) Kirchhoff index has attracted a lot of attention from researchers over the few years. Furthermore, its closed-form formulae have been established depending on many kinds of graphs. For examples, the formulae of Kirchhoff index for cycles, circulant graphs, and composite graphs were obtained in [15, 16] and [17], respectively, and those of both indices for complete multipartite graphs were obtained in [18]. Besides, quite a few literature concerned the (multiplicative degree-) Kirchhoff index of polygon chains and their variants. Explicit expressions of the above index have been derived for linear polyomino chain [19], linear crossed polyomino chain [20], linear pentagonal chain [21], linear phenylenes [22, 23], cyclic phenylenes [24], Möbius phenylenes chain and cylinder phenylenes chain [25, 26], linear (n) phenylenes [27], generalized phenylenes [28, 29], linear hexagonal chain [30, 31], linear crossed hexagonal chain [32], Möbius hexagonal chain [33], periodic linear chains [34], linear octagonal chain [35], linear octagonal-quadrilateral chain [36], and linear crossed octagonal chain [37].For two disjoint graphsG and H, the strong product of them is written as G⊗H, that is, VG⊗H=VG×VH, and two distinct vertices u1,v1 and u2,v2 are contiguous. The Cartesian product of G and H, written as G×H, is the graph with vertex set VG×VH, and two vertices u1,v1 and u2,v2 are adjacent whenever u1=u2 and v1v2∈EH or v1=v2 and u1u2∈EG. Figure 1 shows the graphs Sn⊗K2 and Sn×K2, where Sn and Kn denote the star and complete graph of order n, severally. Recently, Li et al. [38] determined the expressions of KfSr, Kf∗Sr, and τSr, where Sr is a graph derived from Sn⊗K2 by randomly removing r vertical edges, and τG denotes the number of spanning trees of a connected graph G. Finally, they proposed the problem of determining these three invariants for graphs derived from Sn×K2. In the present study, we completely solve this problem.For convenience, we denoteSn2=Sn×K2. Then, VSn2=2n and ESn2=3n−2. Let E′=ii′|i=1,2,…,n. Sn,r2 will denote the set of graphs derived from Sn2 by discretionarily deleting r edges in E′. Obviously, the unique graph in Sn,n2 is disconnected; hence, we consider Sn,r2 for 0≤r≤n−1 only. Note also, Sn,02=Sn2. In Section 2, some notations and known results are introduced, which will be applied to get our main results. In Section 3, explicit expressions of KfSn2, Kf∗Sn2, and τSn2 are obtained. Finally, KfSn,r2 and τSn,r2 are determined in Section 4, where Sn,r2 is an arbitrary graph in Sn,r2. Moreover, it is shown that limn⟶+∞KfSn2/WSn2=limn⟶+∞KfSn,r2/WSn,r2=8/15 and limn⟶+∞Kf∗Sn2/GutSn2=16/33.Figure 1
The graphsSn⊗K2 and Sn×K2.


## 2. Preliminaries

In this section, we will introduce some basic concepts. These following celebrated definitions and fundamental lemmas can play a vital role in proving our consequences.First, we mark the vertices ofSn2 as in Figure 1; then, set V1=1,2,…,n and V2=1′,2′,…,n′. Therefore, we have(4)LSn2=L11Sn2L12Sn2L21Sn2L22Sn2,ℒSn2=ℒ11Sn2ℒ12Sn2ℒ21Sn2ℒ22Sn2,where LijSn2ℒijSn2 is the submatrix of LSn2 (respectively, ℒSn2) whose rows (columns) correspond to the vertices in Vi (respectively Vj). It is easily seen that L11Sn2=L22Sn2, L12Sn2=L21Sn2, ℒ11Sn2=ℒ22Sn2, and ℒ12Sn2=ℒ21Sn2.Let(5)T=12In12In12In−12In,and then, we have(6)TLSn2T=LASn200LSSn2,TℒSn2T=ℒASn200ℒSSn2,where LASn2=L11Sn2+L12Sn2, LSSn2=L11Sn2−L12Sn2, ℒASn2=ℒ11Sn2+ℒ12Sn2, and ℒSSn2=ℒ11Sn2−ℒ12Sn2.Based on the above arguments, by applying the technique used in [32, 39], we immediately have the following decomposition theorem, where ΦB,λ=λI−B stands for the characteristic polynomial of B.Lemma 3.
LetLASn2, LSSn2, ℒASn2, and ℒSSn2 be written as above. Thus, we obtain that(7)ΦLSn2,λ=ΦLASn2,λΦLSSn2,λ,ΦℒSn2,λ=ΦℒASn2,λΦℒSSn2,λ.Lemma 4 (See [40]).
Assume thatG is a connected graph with n≥2 vertices; then,(8)τG=1n∏i=2nμi.


## 3. Results forSn2

In this section, we will derive explicit expressions ofKfSn2, Kf∗Sn2, and τSn2 as follows.


### 3.1. OnKfSn2 and τSn2

Obviously,(9)L11Sn2=n−1−1…−1−120…0−102…0……………−100…2n×n,L12Sn2=−100…00−10…000−1…0……………000…−1n×n.Hence,(10)LASn2=L11Sn2+L12Sn2=n−1−1−1…−1−110…0−101…0……………−100…1n×n,and we easily have SpLASn2=0,1n−2,n, where ak denotes the k successive a’s.Similarly, we have(11)LSSn2=L11Sn2−L12Sn2=n+1−1−1…−1−130…0−103…0……………−100…3n×n,and get SpLSSn2=2,3n−2,n+2.Hence,SpLSn2=0,1n−2,2,3n−2,n,n+2 from Lemma 3, and we get the following result.Theorem 1.
LetSn2=Sn×K2. Then,(1)
KfSn2=8n3+3n2−14n+12/3n+6(2)
τSn2=n+2⋅3n−2(3)
limn⟶+∞KfSn2/WSn2=8/15Proof.
From Lemma1, we have(12)KfSn2=2nn−2+12+n−23+1n+1n+2=8n3+3n2−14n+123n+2.
From Lemma4, we immediately have(13)τSn2=12n⋅2⋅3n−2⋅n⋅n+2=n+2⋅3n−2.
Finally, we end the proof by confirming thatWSn2=5n2−8n+4. Let wi=∑j∈VSn2dij. Obviously, wi=1⋅n+2n−1=3n−2 if i=1,1′, and wi=1+1+2n−1+3n−2=5n−6 otherwise. Hence,(14)WSn2=12∑i∈VSn2wi=1223n−2+2n−25n−6=5n2−8n+4.


### 3.2. OnKf∗Sn2

Consequently, we will determineKf∗Sn2. Obviously,(15)ℒ11Sn2=1−12n−12n…−12n−12n10…0−12n01…0……………−12n00…1n×n,ℒ12Sn2=−1n00…00−120…000−12…0……………000…−12n×n.Hence,(16)ℒASn2=ℒ11Sn2+ℒ12Sn2=n−1n−12n−12n…−12n−12n120…0−12n012…0……………−12n00…12n×n,and we easily have SpℒASn2=0,1/2n−2,3n−2/2n.Similarly, we have(17)ℒSSn2=ℒ11Sn2−ℒ12Sn2=n+1n−12n−12n…−12n−12n320…0−12n032…0……………−12n00…32n×n,and get SpℒSSn2=2,3/2n−2,n+2/2n.Hence,SpℒSn2=0,1/2n−2,n+2/2n,3n−2/2n,3/2n−2,2 from Lemma 3, and we immediately have the following result.Theorem 2.
LetSn2=Sn×K2. Then,(1)
Kf∗Sn2=48n3+25n2−180n+116/3n+6(2)
limn⟶+∞Kf∗Sn2/GutSn2=16/33Proof.
From Lemma2, it is easily confirmed that(18)Kf∗Sn2=23n−22n−4+2nn+2+2n3n−2+2n−23+12,=48n3+25n2−180n+1163n+6.
Now, letgi=∑j∈VSn2didjdij. Obviously, if i=1,1′, then(19)gi=n⋅2⋅1+n⋅2⋅1⋅n−1+n⋅2⋅2⋅n−1=7n2−6n,and otherwise,(20)gi=2⋅n⋅1+2⋅2⋅1+2⋅n⋅2+2⋅2⋅2⋅n−2+2⋅2⋅3⋅n−2=26n−36.
Hence,(21)GutSn2=12∑i∈VSn2gi=1227n2−6n+26n−362n−2=33n2−68n+36,and it follows that(22)limn⟶+∞Kf∗Sn2GutSn2=limn⟶+∞48n3+25n2−180n+1163n+633n2−68n+36=1633,which completes the proof.


## 3.1. OnKfSn2 and τSn2

Obviously,(9)L11Sn2=n−1−1…−1−120…0−102…0……………−100…2n×n,L12Sn2=−100…00−10…000−1…0……………000…−1n×n.Hence,(10)LASn2=L11Sn2+L12Sn2=n−1−1−1…−1−110…0−101…0……………−100…1n×n,and we easily have SpLASn2=0,1n−2,n, where ak denotes the k successive a’s.Similarly, we have(11)LSSn2=L11Sn2−L12Sn2=n+1−1−1…−1−130…0−103…0……………−100…3n×n,and get SpLSSn2=2,3n−2,n+2.Hence,SpLSn2=0,1n−2,2,3n−2,n,n+2 from Lemma 3, and we get the following result.Theorem 1.
LetSn2=Sn×K2. Then,(1)
KfSn2=8n3+3n2−14n+12/3n+6(2)
τSn2=n+2⋅3n−2(3)
limn⟶+∞KfSn2/WSn2=8/15Proof.
From Lemma1, we have(12)KfSn2=2nn−2+12+n−23+1n+1n+2=8n3+3n2−14n+123n+2.
From Lemma4, we immediately have(13)τSn2=12n⋅2⋅3n−2⋅n⋅n+2=n+2⋅3n−2.
Finally, we end the proof by confirming thatWSn2=5n2−8n+4. Let wi=∑j∈VSn2dij. Obviously, wi=1⋅n+2n−1=3n−2 if i=1,1′, and wi=1+1+2n−1+3n−2=5n−6 otherwise. Hence,(14)WSn2=12∑i∈VSn2wi=1223n−2+2n−25n−6=5n2−8n+4.


## 3.2. OnKf∗Sn2

Consequently, we will determineKf∗Sn2. Obviously,(15)ℒ11Sn2=1−12n−12n…−12n−12n10…0−12n01…0……………−12n00…1n×n,ℒ12Sn2=−1n00…00−120…000−12…0……………000…−12n×n.Hence,(16)ℒASn2=ℒ11Sn2+ℒ12Sn2=n−1n−12n−12n…−12n−12n120…0−12n012…0……………−12n00…12n×n,and we easily have SpℒASn2=0,1/2n−2,3n−2/2n.Similarly, we have(17)ℒSSn2=ℒ11Sn2−ℒ12Sn2=n+1n−12n−12n…−12n−12n320…0−12n032…0……………−12n00…32n×n,and get SpℒSSn2=2,3/2n−2,n+2/2n.Hence,SpℒSn2=0,1/2n−2,n+2/2n,3n−2/2n,3/2n−2,2 from Lemma 3, and we immediately have the following result.Theorem 2.
LetSn2=Sn×K2. Then,(1)
Kf∗Sn2=48n3+25n2−180n+116/3n+6(2)
limn⟶+∞Kf∗Sn2/GutSn2=16/33Proof.
From Lemma2, it is easily confirmed that(18)Kf∗Sn2=23n−22n−4+2nn+2+2n3n−2+2n−23+12,=48n3+25n2−180n+1163n+6.
Now, letgi=∑j∈VSn2didjdij. Obviously, if i=1,1′, then(19)gi=n⋅2⋅1+n⋅2⋅1⋅n−1+n⋅2⋅2⋅n−1=7n2−6n,and otherwise,(20)gi=2⋅n⋅1+2⋅2⋅1+2⋅n⋅2+2⋅2⋅2⋅n−2+2⋅2⋅3⋅n−2=26n−36.
Hence,(21)GutSn2=12∑i∈VSn2gi=1227n2−6n+26n−362n−2=33n2−68n+36,and it follows that(22)limn⟶+∞Kf∗Sn2GutSn2=limn⟶+∞48n3+25n2−180n+1163n+633n2−68n+36=1633,which completes the proof.


## 4. Results for Graphs inSn,r2

Assume thatSn,r2 is any graph in Sn,r2, 1≤r≤n−1. We will carry out a computational study on KfSn,r2 and τSn,r2 in this section.We suppose thatdi is the degree of i in Sn,r2. Therefore, di=n or n−1 if i=1,1′, and di=1 or 2 otherwise. We will compute SpSn,r2 in the following.Case 1. Edge11′∉En,r2. Then,(23)L11Sn,r2=n−1−1−1…−1−1d20…0−10d3…0……………−100…dn,L12Sn,r2=000…00t20…000t3…0……………000…tn,where ti=0 if di=1 and ti=1 if di=2, 2≤i≤n. Hence,(24)LASn,r2=L11Sn,r2+L12Sn,r2=n−1−1−1…−1−110…0−101…0……………−100…1n×n,and SpLASn,r2=0,1n−2,n. On the other hand,(25)LSSn,r2=L11Sn,r2−L12Sn,r2=n−1−1−1…−1−1d2−t20…0−10d3−t3…0……………−100…dn−tn,where di−ti=1 if di=1 and di−ti=3 if di=2, 2≤i≤n. We will compute SpLSSn,r2 in the following cases.Case 1.1.r=1. Then, di−ti=3, 2≤i≤n, and we easily have(26)SpLSSn,r2=3n−2,n+2+n2−4n+122,n+2−n2−4n+122.Case 1.2.r≥2. By direct calculations, we have(27)ΦLSSn,r2,λ=λ3−n+3λ2+3nλ+2r−2nλ−1r−2λ−3n−r−1.Letλ1,λ2,λ3 be the three roots of λ3−n+3λ2+3nλ+2r−2n=0. Then, SpLSSn,r2=1r−2,3n−r−1,λ1,λ2,λ3, and it holds that λ1λ2λ3=2n−2r and(28)1λ1+1λ2+1λ3=λ1λ2+λ1λ3+λ2λ3λ1λ2λ3=3n2n−2r,Case 2.11′∈En,r2. Then,(29)L11Sn,r2=n−1−1…−1−1d20…0−10d3…0……………−100…dn,L12Sn,r2=−100…00t20…000t3…0……………000…tn,where ti=0 if di=1 and ti=−1 if di=2, 2≤i≤n. Hence,(30)LASn,r2=L11Sn,r2+L12Sn,r2=n−1−1−1…−1−110…0−101…0……………−100…1n×n,and SpLASn,r2=0,1n−2,n. On the other hand,(31)LSSn,r2=L11Sn,r2−L12Sn,r2=n+1−1−1…−1−1d2−t20…0−10d3−t3…0……………−100…dn−tn,where di−ti=1 if di=1 and di−ti=3 if di=2, 2≤i≤n. By direct calculations, we have(32)ΦLSSn,r2,λ=λ3−n+5λ2+3n+8λ+2r−2n−4λ−1r−1λ−3n−r−2.Letλ1,λ2,λ3 be the three roots of λ3−n+5λ2+3n+8λ+2r−2n−4=0. Then, SpLSSn,r2=1r−1,3n−r−2,λ1,λ2,λ3, and it holds that λ1λ2λ3=2n−2r+4 and(33)1λ1+1λ2+1λ3=λ1λ2+λ1λ3+λ2λ3λ1λ2λ3=3n+82n−2r+4,from Vieta’s theorem.Now, we are able to give the main result of this section.Theorem 3.
IfSn,r2∈Sn,r2, 0≤r≤n−1, then(1)
KfSn,r2=8n3−4r+17n2−4r2−26r−6n−6r/3n−r,if11′∉ESn,r2,8n3−4r−3n2−4r2−30r+14n+12−6r/3n−r−2,if11′∈ESn,r2.(2)
τSn,r2=n−r⋅3n−r−1,if11′∉ESn,r2,n−r+2⋅3n−r+2,if11′∈ESn,r2,(3)
limn⟶+∞KfSn,r2/WSn,r2=8/15Proof.
Ifr=0, then Sn,r2≅Sn2, and the conclusion holds from Theorem 1. Hence, assume r≥1. We distinguish the following two cases.Case 1. Edge11′∉En,r2.Case 1.1.r=1. Then,(34)SpLSn,r2=0,1n−2,n,3n−2,n+2−n2−4n+122,n+2+n2−4n+122.From Lemma1, we have(35)KfSn,r2=2nn−2+1n+n−23+2n+2−n2−4n+12+2n+2+n2−4n+12,=8n3−21n2+28n−63n−1=8n3−4r+17n2−4r2−26r−6n−6r3n−r.Then, from Lemma2, we have(36)τSn,r2=12nn⋅3n−2⋅n+2−n2−4n+122⋅n+2+n2−4n+122,=n−1⋅3n−2=n−r⋅3n−r−1.Case 1.2.r≥2. Then, SpLSn,r2=0,1n+r−4,n,3n−r−1,λ1,λ2,λ3, where λ1λ2λ3=2n−2r and 1/λ1+1/λ2+1/λ3=3n/2n−2r. From Lemma 1, we have(37)KfSn,r2=2nn+r−4+1n+n−r−13+3n2n−2r,=8n3−4r+17n2−4r2−26r−6n−6r3n−r.Then, from Lemma2, we have(38)τSn,r2=n⋅3n−r−1⋅λ1⋅λ2⋅λ32n=n⋅3n−r−1⋅2n−2r2n=n−r⋅3n−r−1.Case 2. Edge11′∈En,r2. Then, SpLSn,r2=0,1n+r−3,n,3n−r−2,λ1,λ2,λ3, where λ1λ2λ3=2n−2r+4 and 1/λ1+1/λ2+1/λ3=3n+8/2n−2r+4. From Lemma 1, we have(39)KfSn,r2=2nn+r−3+1n+n−r−23+3n+82n−2r+4,=8n3−4r−3n2−4r2−30r+14n+12−6r3n−r+2.
Then, from Lemma2, we have(40)τSn,r2=n⋅3n−r−2⋅λ1⋅λ2⋅λ32n=n⋅3n−r−2⋅2n−2r+42n=n−r+2⋅3n−r−2.
Finally, it is straightforward to haveWSn,r2=WSn2+r=5n2−8n+r+4. Hence, in both cases, it holds that(41)limn⟶+∞KfSn,r2WSn,r2=815.



---

*Source: 1670984-2022-02-17.xml*