Open Journal of Discrete Mathematics, 2012, 2, 156-159
http://dx.doi.org/10.4236/ojdm.2012.24031 Published Online October 2012 (http://www.SciRP.org/journal/ojdm)
Cycles, the Degree Distance, and the Wiener Index*
Daniel Gray1, Hua Wang2#
1Department of Mathematics, University of Florida, Gainesville, USA
2Department of Mathematical Sciences, Georgia Southern University, Statesboro, USA
Received July 30, 2012; revised September 3, 2012; accepted September 11, 2012
ABSTRACT
The degree distance of a graph G is
 
,
11
1
2
nn
iji
ij
DGdd L


 j
, where and
i
d
j
d are the degrees of vertices
, and is the distance between them. The Wiener index is defined as

,
ij
vv VG,ij
L

,
11
1
2
nn
ij
ij
WG L

 . An
elegant result (Gutman; Klein, Mihalić,, Plavšić and Trinajstić) is known regarding their correlation, that
 
4DTWT nn
1 for a tree T with n vertices. In this note, we extend this study for more general graphs that
have frequent appearances in the study of these indices. In particular, we develop a formula regarding their correlation,
with an error term that is presented with explicit formula as well as sharp bounds for unicyclic graphs and cacti with
given parameters.
Keywords: Degree Distance; Wiener Index; Cacti
1. Introduction
The Wiener index of a graph is the sum of the
distances between all pairs of vertices, denoted by
G

,
11
1
2
nn
ij
ij
WG L

 where is the distance be-
,ij
L
tween two vertices

 
12
,:,,
ij n
vv VGvvv,. Such
topological indices are defined as molecular descriptors
that describe the structure/shape of molecules, helping to
predict the activity and properties of molecules in com-
plex experiments. Among these indices,


WG was
introduced by and named after Wiener [1] as one of the
most well-known such concepts.
Dobrynin and Kochetova [2] introduced the degree
distance as a “degree analogue of the Wiener index”, de-
noted by
 


,
11
,
11
1
2
nn
ijij
ij
nn
iij
ij
DGdd L
dL






where is the degree of the vertex .
i
The properties of and of various
types of graphs are vigorously studied, see for instance
[3-9] and the references there for such results on trees,
unicyclic and bicyclic graphs, and cacti. In many cases
their extremal values are achieved by the same structures.
Then it is natural to consider the correlation between
di v

WG

DG


WG and


DG
. An elegant result for trees was
achieved in as early as 1992, that
Theorem 1.1. ([10,11])
 


41DTWT nn

for a tree T with n vertices.
We generalize Theorem 1.1 to unicyclic graphs and
cacti in general. In Section 2, we provide an observation
where an “error term” is defined to simplify notations.
With this observation, we provide the relation between


DT

and


WT for unicyclic graphs and cacti in
Section 3.
2. The “Error Term” and a Simple
Observation
Theorem 1.1 also follows from the fact that


0eT

(for a tree ) in the following:
T
Lemma 2.1. Let an “error term”be






2 1DGnEG nn

:4G WeG

 . Then


 
,
11
11 2
ii j i
ij
ji
eGdLd WG








 . (1)
nn
*This work was partially supported by a grant from the Simons Founda-
tion (#245307 to Hua Wang).
#Corresponding author. Proof. From the definition we have
C
opyright © 2012 SciRes. OJDM

D. GRAY, H. WANG 157
  

 



 

 
,,
11
,
11
2
,
11
=11
112
2
11
22 1.
nn
iijiji
ij
nn
iij
ij
nn
iiji
ij
ji
DGdLL d
dL WG
nE Gn
dL d
WGnEG nn













 



1





To understand (1), note that for any two non-adjacent
vertices
x
and in , the sum y

VG
 
 
,
11
,
11 1
11
11
nn
iiji
ij
ji
nn n
iij
ij i
ji
dL d
dL


 














 i
d


y
en
(2)
counts the distance between x and y once when vi is a
neighbor of x on the shortest path between x and y and
j, and once when i is a neighbor of y on the
shortest path between x and y and j. When i is
summed over all i we get twice the number of edges,
which double counts all pairs of vertices distance 1 apart.
v
vvxd
Throughout this note, we will focus on the distances
that are counted more than twice in (2), the sum of which
gives us . Theorem 1.1 follows from Lemma 2.1
through the fact that all distances are counted exactly
twice in a tree. Also, note that the sum of distances of
pairs of adjacent vertices are counted exactly twice by
1. Hence, we only need to consider the distances
between non-adjacent vertices.

eG
n
i
id


3. Unicyclic Graphs and Cacti
In this section, we extend this result to unicyclic graphs
and cacti. Although the unicyclic graphs can be con-
sidered as a special case of cacti, it is convenient to
illustrate the proof by studying a unicyclic graph first.
The “error term”

eG ables us to present the general
formula in a “neat” manner, then we focus on its explicit
form and bounds.

A cactus is a connected graph where any two
cycles share at most one vertex. Trees, cycles, and
unicyclic graphs are all special cases of cacti. Let
G
s
be
the number of cycles in , then in cycles and
unicyclic graphs.
G1s
3.1. Unicyclic Graphs
Theorem 3.1. for a
unicyclic graph on vertices.
 
41DGWG nneG

Gn

 

2
21
11
nn e
nn




G

 (3)
where

is the length of the unique cycle.
Proof. The formula for follows immediately
since

DG





==EGGV n
.
1) We first establish a formula for


eG . Let
12
,,,
x
xx

 be the vertices on the cycle labeled in a
clockwise fashion and let 12
,,,
X
XX

 be the
corresponding components after removing all edges on
the cycle. Note that k
X
is a tree for 1,k2, ,

.
First notice that the distances between any two vertices
in k
X
are counted exactly twice since k
X
is a tree, for
1, 2,,k


. Suppose that ik and vX
j
l
vX

, and
1<kl


. For ik vx

, the shortest paths between
j
v and all but one neighbors of i v must contain the
shortest path from i to v
j
v. Then the distance between
j
v and all neighbors of i not on the path between v
j
v
and is counted exactly twice.
i
v
If , let
=vx
ik

be even (the case for odd

is si-
milar). If 2
2
lk


 or 2
2
lk

 , then the short-
est paths between
j
v and all but one neighbors of k
x
must contain the shortest path from k
x
to
j
v. Then the
distance between
j
v and any vertex adjacent to k
x
not
on the shortest path between
j
v and k
x
is counted
exactly twice.
When 1
2
lk


, the distance between
j
v and any
neighbor of k
x
in


VX are counted twice as above.
k
However, the distance between 1k
x
 and
j
v is counted
as





1,1,,
,
2
kjkl lj
lj
Lx vLxxLxv
Lxv





,Lvu
distanc
where is the distance between and . Note v u
that thise is also counted for the case
1
2
lk


, hence over counted once for every


j
l
vVX


eG. Then the total contribution to as l
ranges from 1 to

is




1
1
,
2
,.
2
l
lvV X
l
l
lvVX
l
Lxv
nLxv

















When 2 lk


, the distance between 1k
x

or 1k
x

is miscounted once as

1,
2l
Lxv .

and


j
l
vVX

D. GRAY, H. WANG 158
Then the contribution to is given by 3.2.


eG
G
for General Cacti

eG




1
1
1,.
2
l
l
lvVX
l
nLxv












Then
1
Here xv is often referred to as the
of
Let be a cactus with
s
cycles and r edges not on
any cycle. Label the cycles c

for 1, 2,,
s

, let


be the length of c

and l
x

be a vertex on c

with component l
X

(the component containing l
x

after the removal of the edges on c

) for 1,2,,l


.
Define the distance function of l
x

by
1
,
2l
lvV X
Lxv





,x
ll
vX
l
DL


v

.


 

1
1
2,
21.
l
lvVX
l
l
l
eGLx vn
Dn










Since


1EGn s

, we immediately have








421DGWG nnseG
.
As was the case for the unicyclic graph, for every
cycle in we have a contribution of
G


,
ll
vVX
l
DL


distance function




1
2,
lj
lvVX
lLx vn



 1


 to


eG. Then an
l
x
in l
X
.
2) Nalue

eG. It is known that, ext we analyze v
f sinimized by the
ce
e th
with given number overtice, explicit formula is given by
l
D is m
by onnter of a star and maximized e end of a path.
Hence


1
11.
ll ll
VXDVX VX



11
11
21
22
s
l
l
s
l
l
eGD n
Dnnrs













1.




(4)
2
The sharp bounds of are given by

eG






 

1
11 .
ll
l
n
VX VXn







The sharp lower bound can be achieved by any cycle
with pendant edges attached, the sharp upper bound can
be
With (4), we claim that, with given and cycle
lengths, the star-shaped cactus (a cactus that has only
one cut vertex as its center) minimizes .
,,nsr

eG
1
211
l
l
VX eG 

 

Claim 3.1. For any cactus with order n, s cycles,
edges and any vertex , there exists a star-
shaped cactus with the same parameters and cycle
lengths with center , such that
G
wVr

G
Su






,,
vVS vVG
LvuLvw



.
achieved by appending a path to a cycle, proving (3). 
In the case of a cycle, 0
l
D

and n

, we have a
simple corollary as follows.
One can easily see the idea from Figure 1, where either
operation from to G
H
will reduce



,
vVGLvw 

Corollary 3.2.
  
44
nnn
DC WC WC
 unless we have a star-shaped cactus.
  
1nn eC
cy rtices, where

n
eC nn
Note that Corollary 3.2 can be directly verifi
n

1
for a
.
ini
Then


eG is minimized when is a star-shaped
cactus. Consequently for all but one , for any
given
G
=0
l
D

l

.
cle n C on n ve
ed from
the deftions,



,,
11 11
,
11
 

11
1
221
1
22
22
s
l
l
s
eGDnn rs
rsnnrs



















11
22
2
nn nn
DGdd LL


 
2
24 .
ij ijij
ij ij
nn
ij
ij
LWG




21.
Figure 1. Two operations that decreases e(G).

D. GRAY, H. WANG 159
Remark 3.3. If one does not specify the cycle lengths,
then bounds similar to the unicyclic case can be achieved.
Also, it is interesting to see that is minimized by a
star-shaped cactus, which miumber of graphi-
cal indices including ([ cacti.
REFERENCES
[1] H. Wiener, “Structural Determination of Paraffin Boiling
Points,” Journal of the American C
69, No. 1, 1947, pp. 17-20. doi:10.10
Vol. 63, No. 1, 2010, pp. 101-112.
[6] M. Fischermann, A. Hoffmann, D. Rautenbach, L. A.
Székely and L. Volkmann, “Wiener Index versus Maxi-
mum Degree in Trees,” Discrete Applied Mathematics,
Vol. 122, No. 1-3, 2002, pp. 127-137.
doi:10.1016/S0166-218X(01)00357-2

eG
nimizes a n
7]) among

WG
[7] H. Liu and M. Lu, “A Unified Approach to Cacti for Dif-
ferent Indices,” Match, Vol. 58, No. 1, 2007, pp. 183-194.
[8] A. I. Tomescu, “Properties of Connected Graphs Having
tance,” Discrete Applied Mathe-
, No. 9, 2009, pp. 2745-2748.
hemical Society, Vol.
21/ja01193a005
[2]
on an
008
A. A. Dobrynin and A. A. Kochetova, “Degree Distance
of a Graph: A Degree Analogue of the Wiener Index,”
Journal of Chemical Informatid Computer Sciences,
Vol. 34, No. 5, 1994, pp. 1082-1086.
doi:10.1021/ci00021a
man, S.
“On the Degree Distance of a Graph,” Discrete Applie
Mathematics, p. 2773-2777.
[3] P. Dankelmann, I. Gut Mukwembi and H. C. Swart,
d
Vol. 157, No. 13, 2009, p
doi:10.1016/j.dam.2009.04.006
[4] A. A. Dobrynin, R. Entringer and I. Gutman, “Wiener
Index of Trees: Theory and Applications,” Acta Appli-
candae Mathematicae, Vol. 66, No. 3, 2001, pp. 211-249.
doi:10.1023/A:1010767517079
[5] Z. Du and B. Zhou, “Minimum Wiener Indices of Trees
and Unicyclic Graphs of Given Matching Number,” Match,
Minimum Degree Dis
matics, Vol. 309
doi:10.1016/j.disc.2008.06.031
[9] A. I. Tomescu, “Unicyclic and Bicyclic Graphs Having
Minimum Degree Distance,” Discrete Applied Mathe-
matics, Vol. 156, No. 2, 2008, pp. 125-130.
doi:10.1016/j.dam.2007.09.010
[10] I. Gutman, “Selected Properties of the Schultz Molecular
Topological Index,” Journal of Chemical Information and
Computer Sciences, Vol. 34, No. 5, 1994, pp. 1087-1089.
doi:10.1021/ci00021a009
[11] D. J. Klein, Z. Mihalic′, D. Plavšic′ and N. Trinajstic′,
“Molecular Topological Index: A Relation with the Wie-
ner Index,” Journal of Chemical Information a
puter Sciences, Vol. 32, No. 4, 1
nd Com-
992, pp. 304-305.