×
Hua, Hongbo; Zhang, Shenggui

On the reciprocal degree distance of graphs. (English) Zbl 1242.05060

Discrete Appl. Math. 160, No. 7-8, 1152-1163 (2012).
Summary: We study a new graph invariant named reciprocal degree distance (RDD), defined for a connected graph \(G\) as -weighted sum of the reciprocal distances, that is,
\[ RDD(G)=\sum_{\{u,v\}\subset V(G)}(d_{G}(u)+d_{G}(v)) \frac {1}{d_{G}(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 . 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, 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, , chromatic number and vertex-, and .
© Elsevier B.V.

Cited in 2 Reviews
Cited in 35 Documents

MSC:

05C07 Vertex degrees
05C12 Distance in graphs
05C35 Extremal problems in graph theory

Keywords:

distance (in graphs); degree distance; reciprocal degree distance; bounds; extremal graphs
Cite Review PDF
Full Text: DOI

References:

[1] Ashrafi, A. R.; Došlić, T.; Hamzeha, A., The Zagreb coindices of graph operations, Discrete Appl. Math., 158, 1571-1578, 2010 · Zbl 1201.05100
[2] Ashrafi, A. R.; Došlić, T.; Hamzeha, A., Extremal graphs with respect to the Zagreb coindices, MATCH Commun. Math. Comput. Chem., 65, 85-92, 2011 · Zbl 1265.05135
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications, 1976, Macmillan London and Elsevier: Macmillan London and Elsevier New York · Zbl 1226.05083
[4] Bucicovschia, O.; Cioabaˇ, S. M., The minimum degree distance of graphs of given order and size, Discrete Appl. Math., 156, 3518-3521, 2008 · Zbl 1168.05308
[5] Dankelmann, P.; Gutman, I.; Mukwembi, S.; Swart, H. C., On the degree distance of a graph, Discrete Appl. Math., 157, 2773-2777, 2009 · Zbl 1209.05069
[6] Das, K. C.; Zhou, B.; Trinajstić, N., Bounds on Harary index, J. Math. Chem., 46, 1369-1376, 2009 · Zbl 1194.92080
[7] Dobrynin, A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249, 2001 · Zbl 0982.05044
[8] Dobrynin, A. A.; Kochetova, A. A., Degree distance of a graph: a degree analogue of the Wiener index, J. Chem. Inf. Comput. Sci., 34, 1082-1086, 1994
[9] Du, Z.; Zhou, B., Degree distance of unicyclic graphs, Filomat, 24, 95-120, 2010 · Zbl 1299.05051
[10] Gutman, I., Selected properties of the Schultz molecular topogical index, J. Chem. Inf. Comput. Sci., 34, 1087-1089, 1994
[11] Gutman, I., A property of the Wiener number and its modifications, Indian J. Chem. A, 36, 128-132, 1997
[12] Gutman, I.; Rada, J.; Araujo, O., The Wiener index of starlike trees and a related partial order, MATCH Commun. Math. Comput. Chem., 42, 145-154, 2000 · Zbl 1026.05101
[13] Hosoya, H., A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., 44, 2332-2339, 1971
[14] Hua, H., Zagreb \( M_1\) index, independence number and connectivity in graphs, MATCH Commun. Math. Comput. Chem., 60, 45-56, 2008 · Zbl 1199.05054
[15] Hua, H., Wiener and Schultz molecular topological indices of graphs with specified cut edges, MATCH Commun. Math. Comput. Chem., 61, 643-651, 2009 · Zbl 1224.05115
[16] Ilić, A.; Stevanović, D.; Feng, L.; Yu, G.; Dankelmann, P., Degree distance of unicyclic and bicyclic graphs, Discrete Appl. Math., 159, 779-788, 2011 · Zbl 1222.05040
[17] Ivanciuc, O.; Balaban, T. S.; Balaban, A. T., Reciprocal distance matrix, related local vertex invariants and topological indices, J. Math. Chem., 12, 309-318, 1993
[18] Lucic, B.; Milicevic, A.; Nikolic, S.; Trinajstić, N., Harary index—twelve years later, Croat. Chem. Acta, 75, 847-868, 2002
[19] Plavšć, D.; Nikolić, S.; Trinajstić, N.; Mihalić, Z., On the Harary index for the characterization of chemical graphs, J. Math. Chem., 12, 235-250, 1993
[20] Tomescu, I., Some extremal properties of the degree distance of a graph, Discrete Appl. Math., 98, 159-163, 1999 · Zbl 0936.05038
[21] A.I. Tomescu, Minimal graphs with respect to the degree distance, Technical Report, University of Bucharest, 2008. Available online at: http://sole.dimi.uniud.it/ alexandru.tomescu/files/dd-distance.pdf.
[22] Tomescu, I., Properties of connected graphs having minimum degree distance, Discrete Math., 309, 2745-2748, 2008 · Zbl 1182.05076
[23] Tomescu, A. I., Unicyclic and bicyclic graphs having minimum degree distance, Discrete Appl. Math., 156, 125-130, 2008 · Zbl 1132.05018
[24] Tomescu, I., Ordering connected graphs having small degree distances, Discrete Appl. Math., 158, 1714-1717, 2010 · Zbl 1208.05021
[25] Wiener, H., Structural determination of paraffin boiling point, J. Amer. Chem. Soc., 69, 17-20, 1947
[26] Xu, K., The Zagreb indices of graphs with a given clique number, Appl. Math. Lett., 24, 1026-1030, 2011 · Zbl 1216.05041
[27] K. Xu, K.C. Das, Extremal unicyclic and bicyclic graphs with respect to Harary index, Bull. Malys. Math. Sci. Soc. Article (in press). · Zbl 1267.05276
[28] Xu, K.; Trinajstić, N., Hyper-Wiener indices and Harary indices of graphs with cut edges, Util. Math., 84, 153-163, 2011 · Zbl 1228.05144
[29] Yu, G.; Feng, L., On the maximal Harary index of a class of bicyclic graphs, Util. Math., 82, 285-292, 2010 · Zbl 1232.05069
[30] Zhou, B., Zagreb indices, MATCH Commun. Math. Comput. Chem., 52, 113-118, 2004 · Zbl 1077.05519
[31] Zhou, B., Upper bounds for the Zagreb indices and the spectral radius of series–parallel graphs, Int. J. Quantum Chem., 107, 875-878, 2007
[32] Zhou, B.; Cai, X.; Trinajstić, N., On the Harary index, J. Math. Chem., 44, 611-618, 2008 · Zbl 1217.05216
[33] Zhou, B.; Trinajstić, N., On reciprocal molecular topological index, J. Math. Chem., 44, 235-243, 2008 · Zbl 1145.92347
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.