### Journal Menu >>

 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 Email: dgray1@ufl.edu, #hwang@georgiasouthern.edu Received July 30, 2012; revised September 3, 2012; accepted September 11, 2012 ABSTRACT The degree distance of a graph G is ,1112nnijiijDGdd L j, where and idjd are the degrees of vertices , and is the distance between them. The Wiener index is defined as ,ijvv VG,ijL,1112nnijijWG 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,1112nnijijWG L where is the distance be- ,ijLtween two vertices 12,:,,ij nvv 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,1112nnijijijnniijijDGdd LdL where is the degree of the vertex . iThe 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 div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: TLemma 2.1. Let an “error term”be 2 1DGnEG nn:4G WeG . Then ,1111 2iij iijjieGdLd 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 Copyright © 2012 SciRes. OJDM D. GRAY, H. WANG 157 ,,11,112,11=1111221122 1.nniijijiijnniijijnniijiijjiDGdLL ddL WGnE GndL dWGnEG nn 1 To understand (1), note that for any two non-adjacent vertices x and in , the sum yVG,11,11 11111nniijiijjinn niijij ijidL ddL  idyen (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dThroughout 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. eGniid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 Gs 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 22111nn enn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,,,xxx be the vertices on the cycle labeled in a clockwise fashion and let 12,,,XXX be the corresponding components after removing all edges on the cycle. Note that kX is a tree for 1,k2, ,. First notice that the distances between any two vertices in kX are counted exactly twice since kX is a tree, for 1, 2,,k. Suppose that ik and vXjlvX, and 1