On Harary index of graphs. (English) Zbl 1228.05143
Summary: The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph \(G=(V,E)\) and two nonadjacent vertices \(v_{i}\) and \(v_{j}\) in \(V(G)\) of \(G\), recall that \(G+v_{i}v_{j}\) is the supergraph formed from \(G\) by adding an edge between vertices \(v_{i}\) and \(v_{j}\). Denote the Harary index of \(G\) and \(G+v_{i}v_{j}\) by \(H(G)\) and \(H(G+v_{i}v_{j})\), respectively. We obtain lower and upper bounds on \(H(G+v_{i}v_{j}) - H(G)\), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.
References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan Press: Macmillan Press New York · Zbl 1134.05001 |
| [2] | Cai, X.; Zhou, B., Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs, Discrete Appl. Math., 157, 3046-3054 (2009) · Zbl 1211.05034 |
| [3] | Das, K. C.; Gutman, I.; Zhou, B., New upper bounds on Zagreb indices, J. Math. Chem., 46, 514-521 (2009) · Zbl 1200.92048 |
| [4] | Das, K. C.; Zhou, B.; Trinajstić, N., Bounds on Harary index, J. Math. Chem., 46, 1369-1376 (2009) |
| [5] | Diudea, M. V., Indices of reciprocal properties or Harary indices, J. Chem. Inf. Comput. Sci., 37, 292-299 (1997) |
| [6] | Dobrynin, A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249 (2001) · Zbl 0982.05044 |
| [7] | Dobrynin, A.; Gutman, I.; Klavžar, S.; Žigert, P., Wiener index of hexagonal systems, Acta Appl. Math., 72, 247-294 (2002) · Zbl 0993.05059 |
| [8] | Estrada, E.; Rodriguez, L., Matrixalgebraic manipulation of molecular graphs. 2. Harary- and MTI-like molecular descriptors, MATCH Commun. Math. Comput. Chem., 35, 157-167 (1997) · Zbl 1013.05047 |
| [9] | Feng, L.; Ilić, A., Zagreb, Harary and hyper-Wiener indices of graphs with a given matching number, Appl. Math. Lett., 23, 943-948 (2010) · Zbl 1221.05111 |
| [10] | Gutman, I., A property of the Wiener number and its modifications, Indian J. Chem. Sec. A, 36, 128-132 (1997) |
| [11] | Gutman, I., Relation between hyper-Wiener and Wiener index, Chem. Phys. Lett., 364, 352-356 (2002) |
| [12] | Gutman, I.; Furtula, B., Hyper-Wiener index vs. Wiener index. Two highly correlated structure-descriptors, Monatsh. Math., 134, 975-981 (2003) |
| [13] | Gutman, I.; Furtula, B.; Belić, J., Note on the hyper-Wiener index, J. Serb. Chem. Soc., 68, 943-948 (2003) |
| [14] | (Gutman, I.; Klavžar, S.; Mohar, B., Fiftieth Anniversary of the Wiener Index. Fiftieth Anniversary of the Wiener Index, Discrete Appl. Math., vol. 80 (1997)), 1-113 · Zbl 0883.00010 |
| [15] | (Gutman, I.; Klavžar, S.; Mohar, B., Fifty Years of the Wiener Index. Fifty Years of the Wiener Index, MATCH Commun. Math. Comput. Chem., vol. 35 (1997)), 1-259 |
| [16] | Gutman, I.; Polansky, O. E., Mathematical Concepts in Organic Chemistry (1986), Springer: Springer Berlin, pp. 127-141 · Zbl 0657.92024 |
| [17] | Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals. III. Total \(\pi \)-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972) |
| [18] | Ivanciuc, O., QSAR comparative study of Wiener descriptors for weighted molecular graphs, J. Chem. Inf. Comput. Sci., 40, 1412-1422 (2000) |
| [19] | 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) |
| [20] | Jordán, F.; Báldi, A.; Orci, K. M.; Rácz, I.; Verga, Z., Characterizing the importance of habitat patches and corridors in maintaining the landscape connectivity of a pholidopterac transsylvanica (Orthoptera) metapopulation, Landsc. Ecol., 18, 83-92 (2003) |
| [21] | Joshi, S.; Singh, S.; Agrawal, V. K.; Mathur, K. C.; Karamarkar, S.; Khadikar, P. V., Novel estimation of the edge-shift in X-ray absorption discontinuity by the Harary index (H), Nat. Acad. Sci. Lett., 22, 159-167 (1999) · Zbl 1001.92566 |
| [22] | Klein, D. J.; Lukovits, I.; Gutman, I., On the definition of the hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Sci., 35, 50-52 (1995) |
| [23] | Lučić, B.; Miličević, A.; Nikolić, S.; Trinajstić, N., Harary index—twelve years later, Croat. Chem. Acta, 75, 847-868 (2002) |
| [24] | Plavšić, D.; Nikolić, S.; Trinajstić, N.; Mihalić, Z., On the Harary index for the characterization of chemical graphs, J. Math. Chem., 12, 235-250 (1993) |
| [25] | Randić, M., Novel molecular descriptor for structure-property studies, Chem. Phys. Lett., 211, 478-483 (1993) |
| [26] | Ricotta, C.; Stanisci, A.; Avena, G. C.; Blasi, C., Quantifying the network connectivity of landscape mosaics: a graph-theoretical approach, Community Ecol., 1, 89-94 (2000) |
| [27] | Trinajstić, N., Chemical Graph Theory (1992), CRC Press: CRC Press Boca Raton, FL |
| [28] | Wiener, H., Structural determination of paraffin boiling point, J. Amer. Chem. Soc., 69, 17-20 (1947) |
| [29] | K. Xu, Trees with the seven smallest and eight greatest Harary indices (submitted for publication).; K. Xu, Trees with the seven smallest and eight greatest Harary indices (submitted for publication). · Zbl 1237.05061 |
| [30] | Xu, K.; Trinajstić, N., Hyper-Wiener and Harary indices of graphs with cut edges, Util. Math., 84, 153-163 (2011) · Zbl 1228.05144 |
| [31] | Zhou, B.; Cai, X.; Trinajstić, N., On the Harary index, J. Math. Chem., 44, 611-618 (2008) · Zbl 1217.05216 |
| [32] | Zhou, B.; Cai, X.; Trinajstić, N., On reciprocal complementary Wiener number, Discrete Appl. Math., 157, 1628-1633 (2009) · Zbl 1163.92045 |
| [33] | Zhou, B.; Du, Z.; Trinajstić, N., Harary index of landscape graphs, Int. J. Chem. Model., 1, 35-44 (2008) |
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.
