×

Weighted Harary indices of apex trees and \(k\)-apex trees. (English) Zbl 1316.05030

Summary: If \(G\) is a connected graph, then \(H_A(G) = \sum_{u \neq v}(\deg(u) + \deg(v)) / d(u, v)\) is the additively Harary index and \(H_M(G) = \sum_{u \neq v} \deg(u) \deg(v) / d(u, v)\) the multiplicatively Harary index of \(G\). \(G\) is an apex tree if it contains a vertex \(x\) such that \(G - x\) is a tree and is a \(k\)-apex tree if \(k\) is the smallest integer for which there exists a \(k\)-set \(X \subseteq V(G)\) such that \(G - X\) is a tree. Upper and lower bounds on \(H_A\) and \(H_M\) are determined for apex trees and \(k\)-apex trees. The corresponding extremal graphs are also characterized in all the cases except for the minimum \(k\)-apex trees, \(k \geq 3\). In particular, if \(k \geq 2\) and \(n \geq 6\), then \(H_A(G) \leq(k + 1)(3 n^2 - 5 n - k^2 - k + 2) / 2\) holds for any \(k\)-apex tree \(G\), equality holding if and only if \(G\) is the join of \(K_k\) and \(K_{1, n - k - 1}\).

MSC:

05C07 Vertex degrees
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner-Horev, E., Subdivisions in apex graphs, Abh. Math. Semin. Univ. Hambg., 82, 83-113 (2012) · Zbl 1269.05024
[2] Alizadeh, Y.; Andova, V.; Klavžar, S.; Škrekovski, R., Wiener dimension: fundamental properties and (5,0)-nanotubical fullerenes, MATCH Commun. Math. Comput. Chem., 72, 279-294 (2014) · Zbl 1464.05053
[3] Alizadeh, Y.; Iranmanesh, A.; Došlić, T., Additively weighted Harary index of some composite graphs, Discrete Math., 313, 26-34 (2013) · Zbl 1254.05191
[4] Ashrafi, A. R.; Došlić, T.; Hamzeh, A., The Zagreb coindices of graph operations, Discrete Appl. Math., 158, 1571-1578 (2010) · Zbl 1201.05100
[5] Ashrafi, A. R.; Dos˘lic, T.; Hamzeh, A., Extremal graphs with respect to the Zagreb coindices, MATCH Commun. Math. Comput. Chem., 65, 85-92 (2011) · Zbl 1265.05135
[6] Azari, M.; Iranmanesh, A., Harary index of some nano-structures, MATCH Commun. Math. Comput. Chem., 71, 373-382 (2014) · Zbl 1464.05055
[7] Das, K. C., Maximizing the sum of the squares of the degrees of a graph, Discrete Math., 285, 57-66 (2004) · Zbl 1051.05033
[8] Das, K. C.; Gutman, I., Some properties of the second Zagreb index, MATCH Commun. Math. Comput. Chem, 52, 103-112 (2004) · Zbl 1077.05094
[9] Deng, H., A unified approach to the extremal Zagreb indices for trees, unicyclic graphs and bicyclic graphs, MATCH Commun. Math. Comput. Chem., 57, 597-616 (2007) · Zbl 1199.05052
[10] Deng, H.; Krishnakumari, B.; Venkatakrishnan, Y. B.; Balachandran, S., Multiplicatively weighted Harary index of graphs, J. Comb. Optim. (2015), in press · Zbl 1327.05067
[11] 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)
[12] Gutman, I., Selected properties of the Schultz molecular topogical index, J. Chem. Inf. Comput. Sci., 34, 1087-1089 (1994)
[13] Gutman, I.; Ruščić, B.; Trinajstić, N.; Wilcox, C. F., Graph theory and molecular orbitals. XII. Acyclic polyenes, J. Chem. Phys., 62, 3399-3405 (1975)
[14] Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals. III. Total \(\pi \)-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972)
[15] Hua, H.; Wang, M., On Harary index and traceable graphs, MATCH Commun. Math. Comput. Chem., 70, 297-300 (2013) · Zbl 1299.05091
[16] Hua, H.; Zhang, S., On the reciprocal degree distance of graphs, Discrete Appl. Math., 160, 1152-1163 (2012) · Zbl 1242.05060
[17] Ilić, A.; Klavžar, S.; Stevanović, D., Calculating the degree distance of partial Hamming graphs, MATCH Commun. Math. Comput. Chem., 63, 411-424 (2010) · Zbl 1265.05186
[18] Ivanciuc, O.; Balaban, T. S.; Balaban, A. T., Design of topological indices. Part 4. Reciprocal distance matrix, related local vertex invariants and topological indices, J. Math. Chem., 12, 309-318 (1993)
[19] Liu, M.; Liu, B., The second Zagreb indices of unicyclic graphs with given degree sequences, Discrete Appl. Math., 167, 217-221 (2014) · Zbl 1284.05066
[20] Lučić, B.; Sović, I.; Plavšić, D.; Trinajstić, N., Harary matrices: Definitions, properties and applications, (Gutman, I.; Furtula, B., Distance in Molecular Graphs—Applications (2012), University of Kragujevac: University of Kragujevac Kragujevac), 3-26
[21] Mihalić, Z.; Trinajstić, N., A graph-theoretical approach to structure-property relationship, J. Chem. Educ., 69, 701-712 (1992)
[22] Mohar, B., Apex graphs with embeddings of face-width three, Discrete Math., 176, 203-210 (1997) · Zbl 0891.05026
[23] Niu, J.; Zhang, C. Q., Cliques, minors and apex graphs, Discrete Math., 309, 4095-4107 (2009) · Zbl 1211.05122
[24] Plavšić, D.; Nikolić, S.; Trinajstić, N., On the Harary index for the characterization of chemical graphs, J. Math. Chem., 12, 235-250 (1993)
[26] Su, G.; Xiong, L.; Gutman, I., Harary index of the \(k\)-th power of a graph, Appl. Anal. Discrete Math., 7, 94-105 (2013) · Zbl 1299.05108
[27] Xu, K., The Zagreb indices of graphs with a given clique number, Appl. Math. Lett., 24, 1026-1030 (2011) · Zbl 1216.05041
[28] Xu, K., Trees with the seven smallest and eight greatest Harary indices, Discrete Appl. Math., 160, 321-331 (2012) · Zbl 1237.05061
[29] Xu, K.; Das, K. C., On Harary index of graphs, Discrete Appl. Math., 159, 1631-1640 (2011) · Zbl 1228.05143
[30] Xu, K.; Das, K. C., Extremal unicyclic and bicyclic graphs with respect to Harary index, Bull. Malays. Math. Sci. Soc., 36, 373-383 (2013) · Zbl 1267.05276
[31] Xu, K.; Das, K. C.; Balachandran, S., Maximizing the Zagreb indices of \((n, m)\)-graphs, MATCH Commun. Math. Comput. Chem., 72, 641-654 (2014) · Zbl 1464.05118
[32] Xu, K.; Das, K. C.; Hua, H.; Diudea, M. V., Maximal Harary index of unicyclic graphs with a given matching number, Stud. Univ. Babeş-BolyaiI Chemia, 58, 71-86 (2013)
[33] Xu, K.; Das, K. C.; Trinajstić, N., The Harary Index of a Graph (2015), Springer · Zbl 1365.05005
[34] Xu, K.; Klavžar, S.; Das, K. C.; Wang, J., Extremal \((n, m)\)-graphs with respect to distance-degree-based topological indices, MATCH Commun. Math. Comput. Chem., 72, 865-880 (2014) · Zbl 1464.05209
[35] Xu, K.; Liu, M.; Das, K. C.; Gutman, I.; Furtula, B., A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem., 71, 461-508 (2014) · Zbl 1464.05140
[36] Xu, K.; Wang, J.; Liu, H., The Harary index of ordinary and generalized quasi-tree graphs, J. Appl. Math. Comput., 45, 365-374 (2014) · Zbl 1296.05063
[37] Xu, K.; Zheng, Z.; Das, K. C., Extremal \(t\)-apex trees with respect to matching energy, Complexity (2015), in press
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.