On the reciprocal degree distance of graphs

• Published in: Discrete Applied Mathematics 2012-05, Vol.160 (7-8), p.1152-1163
• Main Authors: Hua, Hongbo, Zhang, Shenggui
• Format: Article
• Language: English
• Subjects: Bounds; Degree distance; Distance (in graphs); Extremal graphs; Graphs; Invariants; Mathematical analysis; Reciprocal degree distance; Trees
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2011.11.032

In this paper, we study a new graph invariant named reciprocal degree distance (RDD), defined for a connected graph G as vertex-degree-weighted sum of the reciprocal distances, that is, RDD(G)=∑{u,v}⊆V(G)(dG(u)+dG(v))1dG(u,v). The reciprocal degree distance is a weight version of the Harary index, just as the degree distance is a weight version of the Wiener index. Our main purpose is to investigate extremal properties of reciprocal degree distance. We first characterize among all nontrivial connected graphs of given order the graphs with the maximum and minimum reciprocal degree distance, respectively. Then we characterize the nontrivial connected graph with given order, size and the maximum reciprocal degree distance as well as the tree, unicyclic graph and cactus with the maximum reciprocal degree distance, respectively. Finally, we establish various lower and upper bounds for the reciprocal degree distance in terms of other graph invariants including the degree distance, Harary index, the first Zagreb index, the first Zagreb coindex, pendent vertices, independence number, chromatic number and vertex-, and edge-connectivity.