# Reformulated Reciprocal Degree Distance and Reciprocal Degree Distance of the Complement of the Mycielskian Graph and Generalized Mycielskian

Authors: Feifei Zhao; Hong Bian; Haizheng Yu; Min Liu
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

The reformulated reciprocal degree distance is defined for a connected graphG as R¯t(G)=(1/2)∑u,υ∈VG((dG(u)+dG(υ))/(dG(u,υ)+t)),t≥0, which can be viewed as a weight version of the t-Harary index; that is, H¯t(G)=(1/2)∑u,υ∈VG(1/(dG(u,υ)+t)),t≥0. In this paper, we present the reciprocal degree distance index of the complement of Mycielskian graph and generalize the corresponding results to the generalized Mycielskian graph.


---

## Body

## 1. Introduction

Throughout this paper we consider (nontrivial) simple graphs, which are finite and undirected graphs without loops or multiple edges. LetG be a connected graph. For vertices u,v∈V(G), the distance between u and v in G, denoted by dG(u,v), is the length of a shortest (u,v)-path in G and let dG(v) be the degree of a vertex v∈V(G). A chemical graph is a graph whose vertices denote atoms and edges denote bonds between those atoms of the underlying chemical structure. A topological index for a (chemical) graph is a real number related to the graph; it does not depend on labeling or pictorial representation of a graph. In theoretical chemistry, molecular structure descriptors (also called topological indices) and graph invariants based on the distances between vertices of a graph or vertex degree are widely used for characterizing molecular graphs, establishing relations between structure and properties of molecules, predicting biological activity of chemical compounds, and making their chemical applications.The Wiener index ofG is defined as W(G)=∑{u,v}∈V(G)dG(u,v) with the summation going over all pairs of distinct vertices of G. Similarly, the Harary index of G is defined as H(G)=1/2∑u,v∈VG(1/dG(u,v)).Das et al. [1] consider the generalized version of Harary index, namely, the t-Harary index, which is defined as H¯t(G)=1/2∑u,v∈VG(1/(dG(u,v)+t)),t≥0. Its applications and mathematical properties are well studied in [2–5].Dobrynin and Kochetova [6] and Gutman [7] independently proposed a vertex-degree-weighted version of Wiener index called degree distance, which is defined for a connected graph G as DD(G)=(1/2)∑u,v∈V(G)(dG(u)+dG(v))dG(u,v). Note that the degree distance is a degree-weight version of the Wiener index. Hua and Zhang [8] introduced a new graph invariant named reciprocal degree distance, which can be as a degree-weight version of Harary index; that is, RDD(G)=(1/2)∑u,v∈VG((dG(u)+dG(v))/dG(u,v)). The reciprocal degree distance of some graph operations is obtained in [9, 10].Recently, Li et al. [11] introduced a vertex-degree-weighted version of t-Harary index called reformulated reciprocal degree distance, which is defined for a connected graph G as R¯t(G)=(1/2)∑u,v∈VG((dG(u)+dG(v))/(dG(u,v)+t)),t≥0. In view of H¯t(G),R¯t(G) is just the additively weighted t-Harary index, while in view of RDD(G) it is also the generalized version of reciprocal degree distance of a connected graph G. The mathematical properties of the three edge-grafting transformations and some sharp upper bounds on the reformulated reciprocal degree distance of trees are presented in [11].The first Zagreb index is defined asM1(G)=∑u∈V(G)dG(u)2=∑uv∈E(G)(dG(u)+dG(v)) and the second Zagreb index is defined as M2(G)=∑u∈V(G)dG(u)2=∑uv∈E(G)(dG(u)dG(v)). The Zagreb indices are found to have applications in QSPR and QSAR studies as well; see [12].Mycielski [13] developed a graph transformation that transforms a graph G into a new graph μ(G), which is called the Mycielskian of G, in a search for triangle-free graphs with arbitrarily large chromatic number. The generalized Mycielskian is natural generalization of Mycielski graphs, which is also called by Tardif cones over graphs [14]. Let G be a graph with vertex set V0={v10,v20,…,vn0} and edge set E0. Given an integer m⩾1, the m-Mycielskian of G, denoted by μm(G), is the graph with vertex set V0∪V1∪V2…∪Vm∪{u}, where Vi={vji:vj0∈V0} is the ith distinct copy of V0 for i=1,2,…,m and edge set E0∪(⋃i=0m-1{vjivj′i+1:vj0vj′0∈E0})∪{υjmu:vjm∈Vm}. Concerning on the other results for (generalized) Mycielskian graph, one can refer to papers [15–19].


## 2. Complement of the Mycielskian Graph

In this section, we obtain the reformulated reciprocal degree distance and reciprocal degree distance of the graphμ¯(G).The following lemmas follow from the structure of the complement of the Mycielskian graph.Lemma 1.
LetG be a connected graph. Then the distances between the vertices of the Mycielskian graph μ¯(G) of G are given as follows. For each x,y∈V((μ¯(G))),(1)
1
d
μ
¯
G
x
,
y
=
1
,
i
f
x
=
u
i
,
y
=
u
j
;
1
,
i
f
x
=
υ
i
,
y
=
υ
j
,
d
G
υ
i
,
υ
j
>
1
;
2
,
i
f
x
=
υ
i
,
y
=
υ
j
,
d
G
υ
i
,
υ
j
=
1
.
2
d
μ
¯
G
x
,
y
=
1
,
i
f
x
=
υ
i
,
y
=
u
j
,
i
=
j
;
1
,
i
f
x
=
υ
i
,
y
=
u
j
,
i
≠
j
,
d
G
υ
i
,
u
j
>
1
;
2
,
i
f
x
=
υ
i
,
y
=
u
j
,
i
≠
j
,
d
G
υ
i
,
u
j
=
1
.
3
d
μ
¯
G
x
,
y
=
2
,
i
f
x
=
u
i
,
y
=
ω
;
1
,
i
f
x
=
υ
i
,
y
=
ω
.Lemma 2.
LetG be a graph on n vertices. Then the degree of any vertex(2)x∈μ¯Gisasfollowing:dμ¯Gx=n,ifx=ω;2n-1-dGυi,ifx=ui;2n-2dGυi,ifx=υi.Remark 3.
LetG be a graph with V(G)={υ1,υ2,…,υn}. Then there are n-1 two element subsets in V(G). Therefore ∑{υi,υj}⊆V(G)(dG(υi)+dG(υj))=∑i=1n(n-1)dG(υi)=2(n-1)m1.Theorem 4 (corresponding to Theorem 3.4 in [20]).
LetG be a graph on n vertices and m1 edges with diameter 2. Then Rt¯(μ¯(G))=(1/(1+t))(8n3-3n2+n-24nm1+4m1+5M1(G))+(1/(2+t))(3n2-n+12nm1-4m1-5M1(G)).Proof.
From the structure of the complement of Mycielskian graph, we consider the following cases of adjacent and nonadjacent pairs of vertices inμ¯(G) to compute Rt¯(μ¯(G)):
(i) If{x,y}⊆U, then (3)∑ui,uj⊆Udμ¯Gui+dμ¯Gujdμ¯Gui,uj+t=∑ui,uj⊆U2n-1-dGυi+2n-1-dGυj1+t;
by Lemmas1 and 2(4)=11+t∑ui,uj⊆U4n-2-dGυi+dGυj=11+tnn-124n-2-2m1n-1=11+tnn-12n-1-2m1n-1.
(ii) If{x,y}⊆V(G), then dμ¯(G)(υi,υj)=1 for each υiυj∈E(G) and dμ¯(G)(υi,υj)=2 otherwise. Therefore(5)∑υi,υj⊑VGdμ¯Gυi+dμ¯Gυjdμ¯Gυi,υj+t=11+t∑υiυj∈EG2n-2dGυi+2n-2dGυj+12+t∑υiυj∈EG2n-2dGυi+2n-2dGυj;
by Lemmas1 and 2(6)=11+t∑υiυj∈EG4n-2∑υi,υj∈EGdGυi+dGυj+12+t∑υi,υj∈EG4n-2∑υiυj∈EGdGυi+dGυj=1t+14nnn-12-m1-22n-1m1-M1G+12+t4nm1-2M1G=11+t2n2n-1-8nm1+4m1+2M1G+12+t4nm1-2M1G.
(iii) Ifx=υi and y=ui, 1≤i≤n, then by Lemmas 1 and 2(7)∑υi,ui⊑Vμ¯Gdμ¯Gυi+dμ¯Guidμ¯Gυi,ui+t=∑i=1ndμ¯Gυi+dμ¯Guidμ¯Gυi,ui+t=11+t∑i=1n2n-2dGυi+2n-1-dGυi=11+t4n-1n-6m1.
(iv) Ifx=υi and y=uj, i≠j, then by Lemmas 1 and 2(8)∑υi,uj⊑Vμ¯G,i≠jdμ¯Gυi+dμ¯Gujdμ¯Gυi,uj+t=11+t∑υi,υj,υiυj∈EG2n-2dGυi+2n-1-dGυj+12+t∑υi,υj,υiυj∈EG2n-2dGυi+2n-1-dGυj=11+t24n-1nn-12-m1-∑υi,υj,υiυj∈EGdGυi+dGυj-∑υi,υj,υiυj∈EGdGυi+12+t24n-1m1-∑υi,υj,υiυj∈EGdGυi+dGυj-∑υi,υj,υiυj∈EGdGυi=11+t4n-1nn-1-2m1-22m1n-1-M1G-2m1n-1-M1G+12+t4n-12m1-2M1G-M1G=11+tnn-14n-1-2m17n-4+3M1G+12+t4n-12m1-3M1G.
Eachυj can be paired with n-1 vertices υi as (υi,υj),i≠j,∑(υi,υj)dG(υj)=(n-1)∑j=1dG(υj)=2m1(n-1).
(v) Ifx=ω and y∈U, then by Lemmas 1 and 2(9)∑ω,ui⊑Vμ¯Gdμ¯Gω+dμ¯Guidμ¯Gω,ui+t=∑i=1ndμ¯Gω+dμ¯Guidμ¯Gω,ui+t=12+t∑i=1nn+2n-1-dGυi=3n-1n-2m12+t.
(vi) Ifx=ω and y∈V(G), then by Lemmas 1 and 2(10)∑ω,υi⊑Vμ¯Gdμ¯Gω+dμ¯Gυidμ¯Gω,υi+t=∑i=1ndμ¯Gω+dμ¯Gυidμ¯Gω,υi+t=11+t∑i=1nn+2n-2dGυi=3n2-4m11+t.
Summarizing the total contributions of above cases of adjacent and nonadjacent pairs of vertices inμ(G), we can obtain the desired result. This completes the proof.Usingt=0 in Theorem 4, we obtain the reciprocal degree distance of the complement of the Mycielskian graph.Corollary 5 (corresponding to Corollary 3.5 in [20]).
LetG be a graph on n vertices and m1 edges with diameter 2. Then RDD(μ¯(G))=8n3-(3/2)n2+(1/2)n-18nm1+2m1+(5/2)M1(G).


## 3. Complement of the Generalized Mycielskian Graph

In this section, we obtain the reformulated reciprocal degree distance and reciprocal degree distance of the graphμ¯m(G).The following lemmas follow from the structure of the complement of the generalized Mycielskian graph.Lemma 6.
LetG be a connected graph. Then the distances between the vertices of the generalized Mycielskian graph μ¯m(G) of G are given as follows. For each u,υ∈V(μ¯m(G))(11)1dμ¯mGu,υ=2,ifu=ui0,υ=uj0,dμmGui0,uj0=1,i,j=1,2,…,n;1,ifu=ui0,υ=uj0,dμmGui0,uj0>1,i,j=1,2,…,n2dμ¯mGu,υ=1,u=uil,υ=ujl,l=1,2,…,m;i,j=1,2,…,n;3dμ¯mGu,υ=2,u=uim,υ=ω,i=1,2,…,n;4dμ¯mGu,υ=1,u=uil,υ=ω,l=0,1,2,…,m-1;i=1,2,…,n;5dμ¯mGu,υ=1,u=uil,υ=uih,l,h=0,1,2,…,m;i=1,2,…,n;l≠h;6dμ¯mGu,υ=2,ifu=uil,υ=ujh,dμmGuil,ujh=1,l≠h,i≠j,l,h=0,1,2,…,m;i,j=1,2,…,n;1,ifu=uil,υ=ujh,dμmGuil,ujh>1,l≠h,i≠j,l,h=0,1,2,…,m;i,j=1,2,…,n.Lemma 7.
LetG be a graph with n vertices. Then the degree of any vertex x∈μ¯m(G) is as follows:(12)dμ¯mGx=nm,ifx=ω;nm+1-2dGui0,ifx=uil,l=0,1…,m-1;i=1,2…,n;nm+1-dGui0-1,ifx=uim,i=1,2…,n.Theorem 8.
LetG be a graph on n vertices and m1 edges with diameter 2. Then Rt¯(μ¯m(G))=(1/1+t)(n3m3+3n3m+3n3m2+n2m2+n3+n-(m2-m-5)M1(G)-2n2m-2m1nm2-18m1nm+6mm1-6m1m2+4m1-2n2-4m1n)+(1/(2+t))(6mm1n+4m1nm2+2m1n+2n2m-4m1+n2-n-(m2-m+5)M1(G)).Proof.
From the structure of the complement of Mycielskian graph, we consider the structure of the complement of generalized Mycielskian and then also consider the following cases of adjacent and nonadjacent pairs of vertices inμ¯m(G) to compute Rt¯(μ¯m(G)).
Case 1. If {u,υ}⊆V(μ¯m(G)),u=ui0,υ=uj0∈V0, then (13)12∑u=ui0,υ=uj0∈V0dμ¯mGui0+dμ¯mGuj0dμ¯mGui0,uj0+t
and by Lemmas6 and 7(14)=12∑u=ui0,υ=uj0∈V0ui0uj0∈EμmGnm+1-2dGui0+nm+1-2dGuj01+t+12∑u=ui0,υ=uj0∈V0ui0uj0∈EμmGnm+1-2dGui0+nm+1-2dGuj02+t=11+t∑u=ui0,υ=uj0∈V0ui0uj0∈EμmG(nm+1-dGui0+dGuj0+12+t∑u=ui0,υ=uj0∈V0ui0uj0∈EμmG(nm+1-dGui0+dGuj0=11+t∑u=ui0,υ=uj0∈V0ui0uj0∈EμmGnm+1-∑u=ui0,υ=uj0∈V0ui0uj0∈EμmG(dGui0+dGuj0+12+t∑u=ui0,υ=uj0∈V0ui0uj0∈EμmGnm+1-∑u=ui0,υ=uj0∈V0ui0uj0∈EμmG(dGui0+dGuj0=21+tnn-12-m1m+1n-2m1n-1-M1G+22+tm1nm+1-M1G.
Case 2. If {u,υ}⊆V(μ¯m(G)), u=uil,υ=ujl∈Vl,l=1,2,…,m, then (15)12∑u=uil,υ=ujl∈Vl;l=1,2,…,mdμ¯mGuil+dμ¯mGujldμ¯mGuil+ujl+tand by Lemmas 6 and 7(16)=12∑u=uil,υ=ujl∈Vl;l=1,2,…,m-1nm+1-2dGui0+nm+1-2dGuj01+t+12∑u=uim,υ=ujm∈Vmnm+1-dGui0-1+nm+1-dGuj0-11+t=121+t∑u=uil,υ=ujl∈Vl;l=1,2,…,m-1(2nm+1-2dGui0+dGuj0+121+t∑u=uim,υ=ujm∈Vm(2nm+1-2-dGui0+dGuj0=11+t∑u=uil,υ=ujl∈Vl;l=1,2,…,m-1nm+1-∑u=uil,υ=ujl∈Vl;l=1,2,…,m-1(dGui0+dGuj0+11+t∑u=uim,υ=ujm∈Vmnm+1-1-12∑u=uim,υ=ujm∈Vm(dGui0+dGuj0=21+tnn-12m-1nm+1-2m1n-1m-1+21+tnn-12nm+1-1-12·2m1n-1.
Case 3. If {u,υ}⊆V(μ¯m(G)), u=uim∈Vm,υ=ω,i=1,2,…,n, then (17)12∑u=uim∈Vm,υ=ω,i=1,2,…,ndμ¯mGuim+dμ¯mGωdμ¯mGuim,ω+tand by Lemmas 6 and 7(18)=12∑u=uim∈Vm,υ=ω,i=1,2,…,nnm+1-1-dGui0+nm2+t=122+t∑u=uim∈Vm,υ=ω,i=1,2,…,nnm+nm+1-1-∑u=uim∈Vm,υ=ω,i=1,2,…,ndGui0=222+tn2nm+n-1-2m1=12+tn2nm+n-1-2m1
Case 4. If {u,υ}⊆V(μ¯m(G)),u=uil∈Vl,υ=ω,l=0,1,…,m-1;i=1,2,…,n, then(19)12∑u=uil∈Vl,υ=ω,l=0,1,…,m-1;i=1,2,…,ndμ¯mGuil+dμ¯mGωdμ¯mGuil,ω+tand by Lemmas 6 and 7(20)=12∑u=uil∈Vl,υ=ω,l=0,1,…,m-1;i=1,2,…,nnm+1-2(dGui0+nm1+t=121+t∑u=uil∈Vl,υ=ω,l=0,1,…,m-1;i=1,2,…,n(2nm+n-2dGui0=121+t∑u=uil∈Vl,υ=ω,l=0,1,…,m-1;i=1,2,…,n2nm+n-2∑u=uil∈Vl,υ=ω,l=0,1,…,m-1;i=1,2,…,ndGui0=221+tnm2nm+n-2·2m1m=11+tnm2nm+n-2·2m1m.
Case 5. If {u,υ}⊆V(μ¯m(G)), u=uil,υ=uih,l≠h;l,h=0,1,…,m;i=1,2…,n, then(21)12∑u=uil,υ=uih;l≠h;l,h=0,1,…,m;i=1,2…,ndμ¯mGuil+dμ¯mGuihdμ¯mGuil,uih+tand by Lemmas 6 and 7(22)=12∑u=uil,υ=uih;l≠h;l,h=0,1,…,m-1;i=1,2…,nnm+1-2dGui0+nm+1-2dGui01+t+12∑u=uil,υ=uim;l=0,1,…,m-1;i=1,2…,nnm+1-2dGui0+nm+1-dGui0-11+t=121+t∑u=uil,υ=uih;l≠h;l,h=0,1,…,m-1;i=1,2…,n(2nm+1-4dGui0+121+t∑u=uil,υ=uim;l=0,1,…,m-1;i=1,2…,n2nm+1-1-3dGui0=121+t∑u=uil,υ=uih;l≠h;l,h=0,1,…,m-1;i=1,2…,n2nm+1-4∑u=uil,υ=uih;l≠h;l,h=0,1,…,m-1;i=1,2…,ndGui0+121+t∑u=uil,υ=uim;l=0,1,…,m-1;i=1,2…,n2nm+1-1)-3∑u=uil,υ=uim;l=0,1,…,m-1;i=1,2…,ndGui0=221+tmm-12n·2nm+1-4mm-12·2m1+221+tnm2nm+1-1-3·2m1m=11+tmm-12n·2nm+1-4mm-12·2m1+11+tnm2nm+1-1-3·2m1m.
Case 6. If {u,υ}⊆V(μ¯m(G)),u=uil,υ=ujh,l≠h;i≠j;l,h=0,1,…,m;i=1,2,…,n, then (23)12∑u=uil,υ=ujh,l≠h;i≠j;l,h=0,1,…,m-1;i,j=1,2,…,ndμ¯mGuil+dμ¯mGujhdμ¯mGuil,ujh+tand by Lemmas 6 and 7(24)=12∑u=uil,υ=ujh,l≠h;i≠j;l,h=0,1,…,m-1;i,j=1,2,…,nnm+1-2dGui0+nm+1-2dGuj0dμ¯mGuil,ujh+t+12∑u=uil,υ=ujm;i≠j;l=0,1,…,m-1;i,j=1,2,…,nnm+1-2dGui0+nm+1-dGuj0-1dμ¯mGuil,ujm+t=12∑u=uil,υ=ujh,l≠h;i≠j;l,h=0,1,…,m-1;i,j=1,2,…,n;uilujh∈EμmG2nm+1-2dGui0+dGuj01+t+12∑u=uil,υ=ujh,l≠h;i≠j;l,h=0,1,…,m-1;i,j=1,2,…,n;uilujh∈EμmG2nm+1-2dGui0+dGuj02+t+12∑u=uil,υ=ujm;i≠j;l=0,1,…,m-1;i,j=1,2,…,n;uilujm∈EμmG2nm+1-1-2dGui0-dGuj01+t+12∑u=uil,υ=ujm;i≠j;l=0,1,…,m-1;i,j=1,2,…,n;uilujm∈EμmG2nm+1-1-2dGui0-dGuj02+t=221+tnn-1mm-12-m-12m12nm+1-2·mm-122m1n-1-M1G+222+tm-1·2m1·2nm+1-2·mm-12·M1G+221+tnn-1-2m1+m-1nn-12nm+1-1-2mn-12m1-M1G-mn-12m1-M1G+222+t2m12nm+1-1-2M1G-M1G;=11+tnn-1mm-12-m-12m12nm+1-mm-12m1n-1-M1G+12+tm-1·2m1·2nm+1-mm-1·M1G+11+tnn-1-2m1+m-1nn-12nm+1-1-2mn-12m1-M1G-mn-12m1-M1G+12+t2m12nm+1-1-2M1G-M1G.Summarizing the total contributions of above cases of adjacent and nonadjacent pairs of vertices in μ¯m(G), we can obtain the desired result; this completes the proof.Usingt=0 in Theorem 8, we obtain the reciprocal degree distance of the complement of the generalized Mycielskian graph.Corollary 9.
LetG be a graph on vertices and m edges with diameter 2. Then (25)RDDμ¯mG=n3m3+3n3m+3n3m2+n2m+n3-15mm1n-3m1n-n2m-3n2-n+3m2-3m-5M1G2+6mm1-6m1m2+2m1



---

*Source: 3764981-2019-01-30.xml*