The general Randić index of trees with given number of pendent vertices. (English) Zbl 1411.05060
Summary: The general Randić index of a graph \(G\) is defined as \(R_\alpha(G) = \sum_{u v \in E(G)}(d(u) d(v))^\alpha\), where \(d(u)\) denotes the degree of a vertex \(u\) in \(G\) and \(\alpha\) is a real number. In this paper, we determine the maximum general Randić indices of trees and chemical trees with \(n\) vertices and \(k\) pendent vertices for \(4 \leq k \leq \lfloor \frac{n + 2}{3} \rfloor\) and \(\alpha_{0} \leq \alpha < 0\), where \(\alpha_0 \approx - 0.5122\) is the unique non-zero root of the equation \(6 \cdot 4^\alpha - 20 \cdot 9^\alpha + 10 \cdot 12^\alpha - 16^\alpha + 5 \cdot 24^\alpha = 0\). The corresponding extremal graphs are also characterized.
MSC:
| 05C07 | Vertex degrees |
| 05C35 | Extremal problems in graph theory |
| 05C90 | Applications of graph theory |
| 92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
References:
| [1] | Al-Fozan, T.; Manuel, P.; Rajasingh, I.; Rajan, R. S., Computing Szeged index of certain nanosheets using partition technique, MATCH Commun. Math. Comput. Chem., 72, 339-353 (2014) · Zbl 1464.05051 |
| [2] | Andriantiana, E. O.D.; Wagner, S.; Wang, H., Maximum Wiener index of trees with given segment sequence, MATCH Commun. Math. Comput. Chem., 75, 91-104 (2016) · Zbl 1461.05035 |
| [3] | Balister, P.; Bollobás, B.; Gerke, S., The generalized Randić index of trees, J. Graph Theory, 56, 270-286 (2007) · Zbl 1134.05017 |
| [4] | Bollobás, B.; Erdös, P., Graphs of extremal weights, Ars Combin., 50, 225-233 (1998) · Zbl 0963.05068 |
| [5] | Borovićanin, B.; Furtula, B., On extremal Zagreb indices of trees with given domination number, Appl. Math. Comput., 279, 208-218 (2016) · Zbl 1410.05021 |
| [6] | Cavers, M.; Fallat, S.; Kirkland, S., On the normalized Laplacian energy and general Randić index \(r_{- 1}\) of graphs, Linear Algebra Appl., 433, 172-190 (2010) · Zbl 1217.05138 |
| [7] | Chen, X.; Qian, J., Conjugated trees with minimum general Randić index, Discr. Appl. Math., 157, 1379-1386 (2009) · Zbl 1172.05312 |
| [8] | Cinkir, Z., Contraction formulas for the Kirchhoff and Wiener indices, MATCH Commun. Math. Comput. Chem., 75, 169-198 (2016) · Zbl 1461.05046 |
| [9] | Clark, L.; Gutman, I., The exponent in the general Randić index, J. Math. Chem., 43, 32-44 (2008) · Zbl 1147.05302 |
| [10] | Das, K. C.; Dehmer, M., Comparison between the zeroth-order Randić index and the sum-connectivity index, Appl. Math. Comput., 274, 585-589 (2016) · Zbl 1410.05105 |
| [11] | Das, K. C.; Mohammed, M. A.; Gutman, I.; Atan, K. A., Comparison between atom-bond connectivity indices of graphs, MATCH Commun. Math. Comput. Chem., 76, 159-170 (2016) · Zbl 1461.05047 |
| [12] | Das, K. C.; Nadjafi-Arani, M. J., Comparison between the Szeged index and the eccentric connectivity index, Discr. Appl. Math., 186, 74-86 (2015) · Zbl 1311.05095 |
| [13] | Dehghan-Zadeh, T.; Ashrafi, A. R.; Habibi, N., Maximum and second maximum of Randić index in the class of tricyclic graphs, MATCH Commun. Math. Comput. Chem., 74, 137-144 (2015) · Zbl 1462.05076 |
| [14] | Devillers, J.; Balaban, A. T., Topological Indices and Related Descriptors in QSAR and QSPR (1999), Gordon and Breach: Gordon and Breach Amsterdam |
| [15] | Estrada, E.; Torres, L.; Rodríguez, L.; Gutman, I., An atom-bond connectivity index: modelling the enthalpy of formation of alkanes, Indian J. Chem., 37A, 849-855 (1998) |
| [16] | Feng, L.; Lan, Y.; Liu, W.; Wang, X., Minimal Harary index of graphs with small parameters, MATCH Commun. Math. Comput. Chem., 76, 23-42 (2016) · Zbl 1461.05052 |
| [17] | Fischermann, M.; Hoffmann, A.; Rautenbach, D.; Volkmann, L., A linear-programming approach to the generalized Randić index, Discr. Appl. Math., 128, 375-385 (2003) · Zbl 1020.05036 |
| [18] | Goubko, M., Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences, MATCH Commun. Math. Comput. Chem., 75, 3-27 (2016) · Zbl 1461.05056 |
| [19] | Goubko, M.; Magnant, C.; Nowbandegani, P. S.; Gutman, I., ABC index of trees with fixed number of leaves, MATCH Commun. Math. Comput. Chem., 74, 697-702 (2015) · Zbl 1462.05081 |
| [20] | Guji, R.; Vumar, E., Bicyclic graphs with maximum general Randić index, MATCH Commun. Math. Comput. Chem., 58, 683-697 (2007) · Zbl 1141.05051 |
| [21] | Gutman, I., A formula for the Wiener number of trees and its extension to graphs containing cycles, Graph Theory Notes N. Y., 27, 9-15 (1994) |
| [22] | Gutman, I.; Furtula, B., Recent Results in the Theory of Randić Index (2008), University of Kragujevac: University of Kragujevac Kragujevac · Zbl 1294.05002 |
| [23] | Gutman, I.; Furtula, B.; Vukićević, Z. K.; Popivoda, G., On Zagreb indices and coindices, MATCH Commun. Math. Comput. Chem., 74, 5-16 (2015) · Zbl 1462.05083 |
| [24] | Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals. Total \(π\)-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972) |
| [25] | Hansen, P.; Mélot, H., Variable neighborhood search for extremal graphs. 6. Analyzing bounds for the connectivity index, J. Chem. Inf. Comput. Sci., 43, 1-14 (2003) |
| [26] | Hu, Y.; Li, X.; Yuan, Y., Trees with minimum general Randić index, MATCH Commun. Math. Comput. Chem., 52, 119-128 (2004) · Zbl 1079.05042 |
| [27] | Hu, Y.; Li, X.; Yuan, Y., Trees with maximum general Randić index, MATCH Commun. Math. Comput. Chem., 52, 129-146 (2004) · Zbl 1089.05069 |
| [28] | Kier, L. B.; Hall, L. H., Molecular Connectivity in Structure-Activity Analysis (1986), Wiley: Wiley New York |
| [29] | Kier, L. B.; Hall, L. H., The meaning of molecular connectivity: a bimolecular accessibility model, Croat. Chem. Acta, 75, 371-382 (2002) |
| [30] | Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993) |
| [31] | Knor, M.; Lužar, B.; Škrekovski, R., Sandwiching the (generalized) Randić index, Discr. Appl. Math., 181, 160-166 (2015) · Zbl 1304.05086 |
| [32] | Li, F.; Ye, Q., The general connectivity indices of fluoranthene-type benzenoid systems, Appl. Math. Comput., 273, 897-911 (2016) · Zbl 1410.05209 |
| [33] | Li, J.; Li, Y., The asymptotic value of the zeroth-order Randić index and sum-connectivity index for trees, Appl. Math. Comput., 266, 1027-1030 (2015) · Zbl 1410.05210 |
| [34] | Li, X.; Gutman, I., Mathematical Aspects of Randić-Type Molecular Structure Descriptors (2006), University of Kragujevac: University of Kragujevac Kragujevac · Zbl 1294.92032 |
| [35] | Li, X.; Liu, J.; Zhong, L., Trees with a given order and matching number that have maximum general Randić index, Discr. Math, 310, 2249-2257 (2010) · Zbl 1205.05052 |
| [36] | Li, X.; Shi, Y., A survey on the Randić index, MATCH Commun. Math. Comput. Chem., 59, 127-156 (2008) · Zbl 1249.05198 |
| [37] | Li, X.; Shi, Y., Corrections of proofs for Hansen and Mélot’s two theorems, Discr. Appl. Math., 155, 2365-2370 (2007) · Zbl 1128.05050 |
| [38] | Li, X.; Shi, Y.; Xu, T., Unicyclic graphs with maximum general Randić index for \(α > 0\), MATCH Commun. Math. Comput. Chem., 56, 557-570 (2006) · Zbl 1274.05079 |
| [39] | Li, X.; Shi, Y.; Zhong, L., Minimum general Randić index on chemical trees with given order and number of pendent vertices, MATCH Commun. Math. Comput. Chem., 60, 539-554 (2008) · Zbl 1199.05043 |
| [40] | Li, X.; Wang, L.; Zhang, Y., Complete solution for unicyclic graphs with minimum general Randić index, MATCH Commun. Math. Comput. Chem., 55, 391-408 (2006) · Zbl 1274.05268 |
| [41] | Li, X.; Yang, Y., Sharp bounds for the general Randić index, MATCH Commun. Math. Comput. Chem., 51, 155-166 (2004) · Zbl 1053.05067 |
| [42] | Li, X.; Zheng, J., Extremal chemical trees with minimum or maximum general Randić index, MATCH Commun. Math. Comput. Chem., 55, 381-390 (2006) · Zbl 1274.05243 |
| [43] | Liu, H.; Lu, M.; Tian, F., Trees of extremal connectivity index, Discr. Appl. Math., 154, 106-119 (2006) · Zbl 1082.05025 |
| [44] | 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) |
| [45] | Qi, X.; Zhou, B.; Du, Z., The Kirchhoff indices and the matching numbers of unicyclic graphs, Appl. Math. Comput., 289, 464-480 (2016) · Zbl 1410.05057 |
| [46] | Rada, J.; Cruz, R., Vertex-degree-based topological indices over graphs, MATCH Commun. Math. Comput. Chem., 72, 603-616 (2014) · Zbl 1464.05106 |
| [47] | Randić, M., On characterization of molecular branching, J. Am. Chem. Soc., 97, 6609-6615 (1975) |
| [48] | Rodríguez, J. M.; Sigarreta, J. M., On the geometric-arithmetic index, MATCH Commun. Math. Comput. Chem., 74, 103-120 (2015) · Zbl 1462.05097 |
| [49] | Rodríguez, J. M.; Sigarreta, J. M., Spectral properties of geometric-arithmetic index, Appl. Math. Comput., 277, 142-153 (2016) · Zbl 1410.05141 |
| [50] | Shi, Y., Note on two generalizations of the Randić index, Appl. Math. Comput., 265, 1019-1025 (2015) · Zbl 1410.05026 |
| [51] | Su, G.; Tu, J.; Das, K. C., Graphs with fixed number of pendent vertices and minimal zeroth-order general Randić index, Appl. Math. Comput., 270, 705-710 (2015) · Zbl 1410.05100 |
| [52] | Tache, R. M., On degree-based topological indices for bicyclic graphs, MATCH Commun. Math. Comput. Chem., 76, 99-116 (2016) · Zbl 1461.05073 |
| [53] | Tomescu, I.; Jamil, M. K., Maximum general sum-connectivity index for trees with given independence number, MATCH Commun. Math. Comput. Chem., 72, 715-722 (2014) · Zbl 1464.05116 |
| [54] | Vukičević, D., Which generalized Randić indices are suitable measures of molecular branching?, Discr. Appl. Math., 158, 2056-2065 (2010) · Zbl 1215.05037 |
| [55] | Vukičević, D.; Furtula, B., Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges, J. Math. Chem., 46, 1369-1376 (2009) · Zbl 1200.92054 |
| [56] | Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17-20 (1947) |
| [57] | Zhang, L.; Lu, M.; Tian, F., Maximum Randić index on trees with \(k\)-pendant vertices, J. Math. Chem., 41, 161-171 (2007) · Zbl 1197.05030 |
| [58] | Zhong, L., General Randić index on trees with a given order and diameter, MATCH Commun. Math. Comput. Chem., 62, 177-187 (2009) · Zbl 1274.05249 |
| [59] | Zhou, B.; Trinajstić, N., On a novel connectivity index, J. Math. Chem., 46, 1252-1270 (2009) · Zbl 1197.92060 |
| [60] | Zhou, B.; Trinajstić, N., On general sum-connectivity index, J. Math. Chem., 47, 210-218 (2010) · Zbl 1195.92083 |
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.
