Extremal trees with given degree sequence for the Randić index. (English) Zbl 1160.05016
Summary: The Randić index of a graph \(G\) is the sum of \(((d(u))(d(v)))^\alpha \) over all edges \(uv\) of \(G\), where \(d(v)\) denotes the degree of \(v\) in \(G, \alpha \neq 0\). When \(\alpha \)=1, it is the weight of a graph. C. Delorme, O. Favaron, and D. Rautenbach [Discrete Appl. Math. 130, No.3, 503–512 (2003; Zbl 1020.05053)] characterized the trees with a given degree sequence with maximum weight, where the question of finding the tree that minimizes the weight is left open. In this note, we characterize the extremal trees with given degree sequence for the Randić index, thus answering the same question for weight. We also provide an algorithm to construct such trees.
Citations:
Zbl 1020.05053References:
| [1] | Delorme, C.; Favaron, O.; Rautenbach, D., Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees, Discrete Appl. Math., 130, 503-512 (2003) · Zbl 1020.05053 |
| [2] | Delorme, C.; Favaron, O.; Rautenbach, D., On the Randić index, Discrete Math., 257, 29-38 (2002) · Zbl 1009.05075 |
| [3] | Gutman, I.; Das, K. C., The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem., 50, 83-92 (2004) · Zbl 1053.05115 |
| [4] | X. Li, I. Gutman, Mathematical Aspects of Randic-type Molecular Structure Descriptors, University of Kragujevac and Faculty of Science Kragujevac, 2006.; X. Li, I. Gutman, Mathematical Aspects of Randic-type Molecular Structure Descriptors, University of Kragujevac and Faculty of Science Kragujevac, 2006. · Zbl 1294.92032 |
| [5] | Liu, H.; Lu, M.; Tian, F., Trees of extremal connectivity index, Discrete Appl. Math., 154, 106-119 (2006) · Zbl 1082.05025 |
| [6] | Nikolić, S.; Kovačević, G.; Miličević, A.; Trinajstić, N., The Zagreb indices 30 years after, Croat. Chem. Acta, 76, 113-124 (2003) |
| [7] | Randić, M., On characterization of molecular branching, J. Amer. Chem. Soc., 97, 6609-6615 (1975) |
| [8] | Rautenbach, D., A note on trees of maximum weight and restricted degrees, Discrete Math., 271, 335-342 (2003) · Zbl 1022.05013 |
| [9] | N. Trinajstić, On Modified Zagreb \(M_2\) index, Reported at the MATH/CHEM/COMP 2002, Dubrovnik, June 24-29, 2002.; N. Trinajstić, On Modified Zagreb \(M_2\) index, Reported at the MATH/CHEM/COMP 2002, Dubrovnik, June 24-29, 2002. |
| [10] | H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, submitted for publication.; H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, submitted for publication. |
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.
