# A Relation betweenD-Index and Wiener Index for r-Regular Graphs

Authors: Ahmed Mohammed Ali; Asmaa Salah Aziz
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

For any two distinct verticesu and v in a connected graph G, let lPu,v=lP be the length of u−v path P and the D–distance between u and v of G is defined as: dDu,v=minplP+∑∀y∈VPdegy, where the minimum is taken over all u−v paths P and the sum is taken over all vertices of u−v path P. The D-index of G is defined as WDG=1/2∑∀v,u∈VGdDu,v. In this paper, we found a general formula that links the Wiener index with D-index of a regular graph G. Moreover, we obtained different formulas of many special irregular graphs.


---

## Body

## 1. Introduction

Throughout this paper, the nontrivial connected graphsG were considered to be finite without multiple edges and loops [1]. As usual, V=VG which denotes the set of vertices of G and E=EG represents the set of edges of G, the order of G is p=pG=VG and the size of G is q=qG=EG. The vertex degree degGv or degv is referred to the number of vertices incident to the vertex v.The standard distance between any two arbitrary verticesu and v of G is the length of a shortest path joining u to v, and it is denoted by dGu,v or du,v. The diameter of a connected graph G denoted by diamG is the length of any longest geodesic [2]. Many researchers have determined different concepts of distances as well as ordinary distance, such as Steiner distance [3], width distance [4], superior distance [5], and signal distance [6]. All distances mentioned above depend on the path length in a connected graph G.In the present work, the concept ofD-distance between distinct vertices of G was considered, in which it depends on the length of a path P as well as the degrees of the vertices that lie on P [7].“The Wiener index of a graphG is represented by WG and defined as the sum of distances between all pairs of vertices in a simple graph G”:(1)WG=12∑∀u,v∈VGdu,v.Based on the Wiener index, Hosoya introduced the Wiener polynomial (now called Hosoya polynomial) in 1988 [8]. The Wiener polynomial WG;x is defined as(2)WG;x=12∑∀u,v∈VGdu,vxdu,v.There are a lot of papers on finding general formulas for Wiener polynomials for different types of distances (see [9, 10]).Definition 1 (see [7]).
“TheD-distance dDu,v between two vertices u and v of a connected graph G is defined as
d
D
u
,
v
=
min
p
l
P
+
∑
∀
y
∈
V
P
deg
y, where lP is the length of u−v path P and the minimum is taken over all u−v paths P in G”.
The totalD-distance or D-index of a connected graph G is defined as(3)WDG=12∑∀v,u∈VGdDu,v.Definition 2 (see [1]).
It can be said that the graphG is r-regular if every vertex in G has r degree, that is, degv=r , for all v∈VG, otherwise the graph G is irregular.Definition 3 (see [1]).
A friendship graphFn is a graph of odd order n, n≥7, which consists of n−1/2 triangles with a common vertex.
LetG1 and G2 be nontrivial disjoint connected graphs, then the Cartesian product graph G1×G2 has vertex set VG1×VG2 and edge set:(4)EG1×G2=u1,v1u2,v2:u1u2∈EG1andv1=v2,orv1v2∈EG2andu1=u2,and the strong product graph G1∗G2 has vertex set VG1×VG2 and edge set:(5)EG1∗G2=u1,v1u2,v2:u1u2∈EG1andv1v2∈EG2,oru1u2∈EG1andv1=v2,orv1v2∈EG2andu1=u2.
There are several papers about theD-distance and the average of this distance, see References [11, 12, 13, 14, 15].
In this work, a relationship between the Wiener index andD-index of any regular graph G was found. Furthermore, the D-index of some special graphs was obtained.


## 2. Preliminaries

In this section, we will mention some of the results that were found previously and others that will be established.Theorem 1 (see [(16]).
(1)
WKn=n2.(2)
WPn=1/6nn2−1.(3)
WCn=n/8n2,ifnis an even,n2−1,ifnis an odd.(4)
WKn,n=n3n2−2.(5)
WQn=n22n−2.Theorem 2 (see [16, 17]).
IfG1 and G2 are nontrivial disjoint connected graphs, then(1)
WG1×G2;x=2WG1;xWG2;x−pG1WG2;x−pG2WG1;x+pG1pG2.(2)
IfWG1;x=∑k=0αakxk and WG2;x=∑k=0βbkxk in which α=diamG1 and β=diamG2. Then, WG1∗G2;x=∑k=0δcxk, where δ=diamG1∗G2=maxα,β, c0=a0b0, c1=a0b1+a1b0+2a1b1, and ck=a0bk+akb0+2ak∑i=1kbi+2bk∑i=1k−1ai.Lemma 1.
Forn≥4, we have(1)
WK2×Cn=1/2n2n+2,ifnis an even,1/2nn2+2n−1,ifnis odd.(2)
WK2∗Cn=1/2n2n+2,ifnis an even,1/2nn2+1,ifnis an odd.Proof.
(1)
From Theorem2 (18), if G1=K2 and G2=Cn, n≥4, then
(6)
W
K
2
×
C
n
;
x
=
2
2
+
x
W
C
n
;
x
−
2
W
C
n
;
x
−
n
2
+
x
+
2
n
=
2
W
C
n
;
x
+
2
x
W
C
n
;
x
−
n
x
.
Taking the derivative with respect tox of both sides and then putting x=1, we get
(7)
W
K
2
×
C
n
=
4
W
C
n
+
n
2
.
From Theorem1 (20), we get
(8)
W
K
2
×
C
n
=
1
2
n
2
n
+
2
,
if
n
is an even,
1
2
n
n
2
+
2
n
−
1
,
if
n
is odd
.
(2)
From Theorem2 (19), if G1=K2 and G2=Cn, n≥4, then
(9)
W
K
2
∗
C
n
;
x
=
2
n
+
5
n
x
+
∑
k
=
2
δ
C
n
4
b
k
x
k
=
4
W
C
n
;
x
−
2
n
+
n
x
.
Taking the derivative with respect tox of both sides and then putting x=1, we get
(10)
W
K
2
∗
C
n
=
4
W
C
n
+
n
.
From Theorem1 (19), we get
(11)
W
K
2
∗
C
n
=
1
2
n
n
2
+
2
,
if
n
is an even,
1
2
n
n
2
+
1
,
if
n
is odd
.


## 3. The Index ofD-Distance for a Connected r-Regular Graph

Theorem 3.
For any connectedr− regular graph G of order n, we have(12)WDG=r+1WG+rn2.Proof.
(13)
W
D
G
=
1
2
∑
u
,
v
∈
V
G
d
D
u
,
v
=
1
2
∑
u
,
v
∈
V
G
min
p
l
P
+
∑
y
∈
V
P
deg
y
=
1
2
∑
u
,
v
∈
V
G
d
u
,
v
+
∑
y
∈
V
P
:
u
−
v
geodessic
deg
y
because is regular
=
1
2
∑
u
,
v
∈
V
G
d
u
,
v
+
1
2
∑
u
,
v
∈
V
G
∑
y
∈
V
P
:
u
−
v
geodesic
deg
y
=
W
G
+
1
2
∑
u
,
v
∈
V
G
∑
y
∈
V
P
:
u
−
v
geodesic
deg
y
.
SinceG is r− regular, then degy=r, ∀y∈VG, and every shortest path between u and v contains du,v+1 vertices with every vertex of degree r.(14)WDG=WG+12∑u,v∈VGdu,v+1r=WG+rWG+r2∑u,v∈VG1=r+1WG+rn2,HenceWDG=r+1WG+rn2.Example 1.
LetG be a Petersen graph of ten orders, as shown in Figure 1.
It is clear thatWPT10=75, then WDPT10=475+3102=435.Figure 1Corollary 1.
(1)
WDKn=2n−1n2.(2)
WDCn=nn−1+3n/8n2,ifnis an even,n2−1,ifnis an odd.(3)
WDKn,n=n5n2−2.(4)
WDQn=n2n2n−1n+3−1.Proof.
From Theorems1 and 3, we get results listed in this corollary.Corollary 2.
Forn≥4, we have(1)
WDK2×Cn=1/2n4n2+11n−3,ifnis  an  even,1/2n4n2+11n−7,ifnis  an  odd.(2)
WDK2∗Cn=1/2n6n2+5n+7,ifnis an even,1/2n6n2+5n+1,ifnis an odd.Proof.
Since fromK2×Cn and K2∗Cn are all 3-regular and 5-regular, respectively, shown Figure 2, then from Lemma 1 and Theorem 3, we get the formulas given in Corollary 2.Figure 2
(a)
(b)


## 4. The Index ofD-Distance for Some Special Graph

n this section, we find theD-index of some special irregular graphs, such as the path graph Pn, n≥2, the star graph Sn, n≥4, the friendship graph Fn, of order odd n, n≥7, the wheel graph Wn, n≥6, and the bipartite complete graph Km,n, m≠n, m,n≥2.Theorem 4.
(1)
WDPn=1/2n3+n2−7/2n+2.(2)
WDSn=1/2n−12n+4.
Proof(1)
LetPn=v1,v2,v3,…,vn−1,vn be a path graph of order n≥2.Sincedv1,vi=i−1, then dDv1,vi=1+3i−1,i=2,3,…,n−1. Also, by symmetric, dDvn,vi=dDv1,vi=1+3i−1, for all i=2,3,…,n−1, and dDv1,vn=3n−1.Sincedvi,vj=j−i, i=2,3,…,n−2,j=i+1,…,n−1, then dDvi,vj=3j−i+2, for all i=2,3,…n−2,j=i+1,…,n−1. Hence,(15)WDPn=∑i=2n−1dDv1,vi+∑i=2n−1dDvn,vi+dDv1,vn+∑i=2n−2∑j=i+1n−1dDvi,vj=3n2−4n−1+∑i=2n−2∑j=i+1n−13j−i+2=3n2−4n−1+3∑i=2n−2∑j=i+1n−1j−i+2∑i=2n−2∑j=i+1n−11=3n2−4n−1+12n3−6n2+11n−6+n2−5n+6=12n3+n2−72n+2.(2)
LetSn be a star graph with order n and let v1 be the center of Sn. It is obvious that(16)dv1,v=1,degv1=n−1,degv=1,∀v∈VSn−v1,thendDv1,v=n+1.Now, since the distance for each pair of end vertices is equal two, thendDu,v=n+3.
Hence,WDSn=n−1n+1+1/2n−1n−2n+3=1/2n−12n+4.Theorem 5.
(1)
WDFn=1/2n−1n2+4n−6.(2)
WDWn=n−1n+3+n−1/2−12n−1/2+3+αn−1,whereα=2n−1,nis an even,n+7/2,nis odd.(3)
WDKm,n=m3+n3+3/2mnn+m−n+m.Proof.
(1)
LetVFn=v1,v2,v3,…,vn, where degv1=n−1 and degvi=2, for all i=2,3,…,n. Then, there are three cases:Case 1: ifv1vi∈EFn,i=2,3,…,n, then dDv1,vi=n+2, for all i=2,3,…,n.Case 2: ifv2iv2i+1∈EFn,i=1,2,…,n−1/2, then dDv2i,v2i+1=5, and the number of pairs of v2i,v2i+1, when v2iv2i+1∈EFn, for all i=1,2,…,n−1/2, is n−1/2.Case 3: ifv2i−1v2i∉EFn, i=2,3,…,n−1/2, then the path P consists from v2i−1,v1,v2i, Hence, dDv2i−1,v2i=n+5. The number of pairs of v2i−1,v2i when v2i−1v2i∉EFn, i=2,3,…,n−1/2, is n−1n−3/2.From the three previous cases, we get(17)WDFn=n−1n+2+5n−12+n+5n−1n−32=n−1n2+4n−6/2.(2)
LetVWn=v1,v2,v3,…,vn, where degv1=n−1 and degvi=3, for all i=2,3,…,n.It is clear that(18)dDv1,vi=n+3.Now, leti<j, for all i,j=2,3,…,n, then there are two cases:Case 1: ifj−i=1,2,…,n−1/2−1, then(19)dDvi,vj=dvi,vj+∑k=ijdegvk=j−i+3∑k=ij1=4j−i+3,where the number of such pairsvi,vj is n−1.Case 2: ifj−i=n−1/2 and n is an even, then(20)dDvi,vj=4n−12+3.Also, the number of such pairsvi,vj is n−1.But whenn is odd, then(21)dDvi,vj=n+7,and the number of such pairs isn−1/2.Hence, from (18)–(21), we have the formula in Theorem 5 part 2.(3)
LetVKm,n=U∪W, where U=u1,u2,…,um and W=w1,w2,…,wn.
The following cases are true in this graph:Case 1: ifv,v′∈U, then dDv,v′=2+2n+m, this is true for all mm−1/2 pairs of vertices.Case 2: ifv,v′∈W, then dDv,v′=2+2m+n, and also this is true for all nn−1/2 pairs of vertices.Case 3: ifv∈U and If v′∈W, then dDv,v′=1+m+n and there are mn pairs of vertices in this case that is true.
From three cases, we conclude that(22)WDKm,n=12m2m+1+n2n+1+2m+n2mn−1−2mn.


## 5. Conclusion

In this paper, we find a general formula giving a relation between the Wiener index andD-index for any regular graph, also we find the D-index for some special graphs.



---

*Source: 6937863-2020-02-22.xml*