×

Comparative study of distance-based graph invariants. (English) Zbl 1475.05044

Summary: The investigation on relationships between various graph invariants has received much attention over the past few decades, and some of these research are associated with Graffiti conjectures [S. Fajtlowicz and W. A. Waller, in: Combinatorics, graph theory, and computing. Proceedings of the 17th Southeastern conference on combinatorics, graph theory, and computing held at Florida Atlantic University (Boca Raton, Florida), February 10–14, 1986. Winnipeg: Utilitas Mathematica Publishing Incorporated. 51–56 (1986; Zbl 0639.05040)] or AutoGraphiX conjectures [M. Aouchiche et al., Nonconvex Optim. Appl. 84, 281–310 (2006; Zbl 1100.90052)]. The reciprocal degree distance (RDD), the adjacent eccentric distance sum (AEDS), the average distance (AD) and the connective eccentricity index (CEI) are all distance-based graph invariants or topological indices, some of which found applications in Chemistry. In this paper, we investigate the relationship between RDD and other three graph invariants AEDS, CEI and AD. First, we prove that AEDS > RDD for any tree with at least three vertices. Then, we prove that RDD > CEI for all connected graphs with at least three vertices. Moreover, we prove that RDD > AD for all connected graphs with at least three vertices. As a consequence, we prove that AEDS > CEI and AEDS > AD for any tree with at least three vertices.

MSC:

05C09 Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
05C35 Extremal problems in graph theory
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, Y.; Klavžar, S., Complexity of topological indices: the case of connective eccentric index, MATCH Commun. Math. Comput. Chem., 76, 659-667 (2016) · Zbl 1461.05034
[2] Aouchiche, M.; Bonnefoy, JM; Fidahoussen, A.; Caporossi, G.; Hansen, P.; Hiesse, L.; Lachere, J.; Monhait, A.; Liberti, L.; Maculan, N., Variable neighborhood search for extremal graphs. 14. The autoGraphiX 2 system, Global Optimization: From Theory to Implementation, 281-310 (2006), New York: Springer, New York · Zbl 1100.90052
[3] Aouchiche, M.; Hansen, P., Proximity and remoteness in graphs: results and conjectures, Networks, 58, 95-102 (2011) · Zbl 1232.05062 · doi:10.1002/net.20450
[4] Bartlett, M.; Krop, E.; Magnant, C.; Mutiso, F.; Wang, H., Variations of distance-based invariants of trees, J. Comb. Math. Comb. Comput., 91, 19-29 (2018) · Zbl 1310.05071
[5] Bielak, H.; Wolska, K., On the adjacent eccentric distance sum of graphs, Ann. UMCS Math., 68, 1-10 (2014) · Zbl 1308.05042
[6] Bondy, JA; Murty, USR, Graph Theory with Applications (1976), New York: Macmillan London and Elsevier, New York · Zbl 1226.05083
[7] Chen, X.; Lian, H., Solution to a problem on the complexity of connective eccentric index of graphs, MATCH Commun. Math. Comput. Chem., 82, 133-138 (2019) · Zbl 1472.92284
[8] Dankelmann, P., Average distance and the domination number, Discrete Appl. Math., 80, 21-35 (1997) · Zbl 0888.05024 · doi:10.1016/S0166-218X(97)00067-X
[9] Dankelmann, P.; Entringer, R., Average distance, minimum degree, and spanning trees, J. Graph Theory, 33, 1-13 (2000) · Zbl 0939.05030 · doi:10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L
[10] Das, KC; Nadjafi-Arani, MJ, Comparison between the Szeged index and the eccentric connectivity index, Discrete Appl. Math., 186, 74-86 (2015) · Zbl 1311.05095 · doi:10.1016/j.dam.2015.01.011
[11] Das, KC; Gutman, I.; Nadjafi-Arani, MJ, Relations between distance-based and degree-based topological indices, Appl. Math. Comput., 270, 142-147 (2015) · Zbl 1410.05040
[12] Das, KC, Comparison between Zagreb eccentricity indices and the eccentric connectivity index, the second geometric-arithmetic index and the Graovac-Ghorbani index, Croat. Chem. Acta, 89, 505-510 (2016) · doi:10.5562/cca3007
[13] Das, KC; Dehmer, M., Comparison between the zeroth-order Randić index and the sum-connectivity index, Appl. Math. Comput., 274, 585-589 (2016) · Zbl 1410.05105
[14] Dobrynin, A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249 (2001) · Zbl 0982.05044 · doi:10.1023/A:1010767517079
[15] Fajtlowicz, S.; Waller, WA, On two conjectures of GRAFFITI II, Congr. Numer., 60, 187-197 (1987)
[16] Gao, XL; Xu, SJ, Average distance, connected hub number and connected domination number, MATCH Commun. Math. Comput. Chem., 82, 57-75 (2019) · Zbl 1472.92299
[17] Ghalavand, A.; Ashrafi, AR, Some inequalities between degree- and distance-based topological indices of graphs, MATCH Commun. Math. Comput. Chem., 79, 399-406 (2018) · Zbl 1472.92301
[18] Gupta, S.; Singh, M.; Madan, AK, Connective eccentricity index: a novel topological descriptor for predicting biological activity, J. Mol. Graph. Model., 18, 18-25 (2000) · doi:10.1016/S1093-3263(00)00027-9
[19] Hua, H.; Zhang, S., On the reciprocal degree distance of graphs, Discrete Appl. Math., 160, 1152-1163 (2012) · Zbl 1242.05060 · doi:10.1016/j.dam.2011.11.032
[20] Hua, H.; Gutman, I.; Wang, H.; Das, KC, Relationships between some distance-based topological indices, Filomat, 32, 5809-5815 (2018) · Zbl 1499.05128 · doi:10.2298/FIL1817809H
[21] Hua, H.; Wang, H.; Gutman, I., Comparing eccentricity-based graph invariants, Discuss. Math. Graph Theory (2018) · Zbl 1446.05023 · doi:10.7151/dmgt.2171
[22] Imran, N.; Shaker, H., Inequalities between degree- and distance-based graph invariants, J. Inequal. Appl., R39, 1-15 (2018) · Zbl 1387.05133
[23] Ivanciuc, O.; Balaban, TS; Balaban, AT, Reciprocal distance matrix, related local vertex invariants and topological indices, J. Math. Chem., 12, 309-318 (1993) · doi:10.1007/BF01164642
[24] Knor, M.; Skrekovski, R.; Tepeh, A., Mathematical aspects of Balaban index, MATCH Commun. Math. Comput. Chem., 79, 685-716 (2018) · Zbl 1472.92313
[25] Li, S.; Meng, X., Four edge-grafting theorems on the reciprocal degree distance of graphs and their applications, J. Comb. Optim., 30, 468-488 (2015) · Zbl 1327.05092 · doi:10.1007/s10878-013-9649-1
[26] Li, S.; Zhang, H.; Zhang, M., Further results on the reciprocal degree distance of graphs, J. Comb. Optim., 31, 648-668 (2016) · Zbl 1331.05114 · doi:10.1007/s10878-014-9780-7
[27] Liu, M.; Das, KC, On the ordering of distance-based invariants of graphs, Appl. Math. Comput., 324, 191-201 (2018) · Zbl 1418.68222 · doi:10.1016/j.cam.2017.05.008
[28] 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) · doi:10.1007/BF01164638
[29] Pourfaraj, L.; Ghorbani, M., Remarks on the reciprocal degree distance, Stud. Univ. Babes-Bolyai Chem., 59, 29-34 (2014)
[30] Qu, H.; Cao, S., On the adjacent eccentric distance sum index of graphs, PloS One, 10, e0129497 (2015) · doi:10.1371/journal.pone.0129497
[31] Sardana, S.; Madan, AK, Predicting anti-HIV activity of TIBO derivatives: a computational approach using a novel topological descriptor, J. Mol. Model., 8, 258-265 (2002) · doi:10.1007/s00894-002-0093-x
[32] Sardana, S.; Madan, AK, Relationship of Wiener’s index and adjacent eccentric distance sum index with nitroxide free radicals and their precursors as modifiers against oxidative damage, J. Mol. Struct. (Theochem), 624, 53-59 (2003) · doi:10.1016/S0166-1280(02)00737-6
[33] Stevanovic, S.; Stevanovic, D., On distance-based topological indices used in architectural research, MATCH Commun. Math. Comput. Chem., 79, 659-683 (2018) · Zbl 1472.92342
[34] Su, G.; Xiong, L.; Su, X.; Chen, X., Some results on the reciprocal sum-degree distance of graphs, J. Comb. Optim., 30, 435-446 (2015) · Zbl 1325.05071 · doi:10.1007/s10878-013-9645-5
[35] Wiener, H., Structural determination of paraffin boiling point, J. Am. Chem. Soc., 69, 17-20 (1947) · doi:10.1021/ja01193a005
[36] Yu, G.; Feng, L., On the connective eccentricity index of graphs, MATCH Commun. Math. Comput. Chem., 69, 611-628 (2013) · Zbl 1299.05112
[37] Yu, G.; Qu, H.; Tang, L.; Feng, L., On the connective eccentricity index of trees and unicyclic graphs with given diameter, J. Math. Anal. Appl., 420, 1776-1786 (2014) · Zbl 1298.05096 · doi:10.1016/j.jmaa.2014.06.050
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.