Randić ordering of chemical trees. (English) Zbl 1071.92050
Summary: We study the behavior of the Randić index \(\chi\) [M. Randić, J. Am. Chem. Soc. 97, 6609–6615 (1975)] subject to the operation on a tree \(T\) which creates a new tree \(T'\neq T\) by deleting an edge \(ax\) of \(T\) and adding a new edge incident to either \(a\) or \(x\). Let \(\preccurlyeq_{\text{mso}}\) be the smallest poset containing all pairs \((T,T')\) such that \(\chi(T)<\chi(T')\) and \(T,T'\in{\mathcal C}_n\) (where \({\mathcal C}_n\) is the collection of trees with \(n\) vertices and of maximum degree 4). We determine the maximal and minimal elements of \(({\mathcal C}_n,\preccurlyeq_{\text{mso}})\). We present an algorithm to construct \(\chi\)-monotone chains of trees \(T_0,T_1,T_2,\dots,T_m\) such that \(T_i \prec_{\text{mso}}T_{i+1}\). As a corollary of our results, we present a new method to calculate the first values of \(\chi\) on \({\mathcal C}_n\).
MSC:
| 92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
| 05C05 | Trees |
| 06A06 | Partial orders, general |
| 05C90 | Applications of graph theory |
Keywords:
connectivity indexSoftware:
AutoGraphiXReferences:
| [1] | A.T.Balaban, O. Ivanciuc, Historical development of topological indices, in: J. Devillers, A.T. Balaban (Eds.), Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach, The Netherlands, 1999, pp. 21-57; A.T.Balaban, O. Ivanciuc, Historical development of topological indices, in: J. Devillers, A.T. Balaban (Eds.), Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach, The Netherlands, 1999, pp. 21-57 |
| [2] | Caporossi, G.; Gutman, I.; Hansen, P., Variable neighborhood search for extremal graphs IV: chemical tress with extremal connectivity index, Comput. Chem., 23, 469-477 (1999) |
| [3] | Caporossi, G.; Gutman, I.; Hansen, P.; Pavlović, L., Graphs with maximum connectivity index, Comput. Biol. Chem., 27, 85-90 (2003) |
| [4] | Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs 1: The system autographix, Discrete Math., 212, 29-44 (2000) · Zbl 0947.90130 |
| [5] | Gutman, I., Two theorems on connectivity indices, J. Serb. Chem. Soc., 67, 99-102 (2002) |
| [6] | Gutman, I.; Araujo, O.; Rada, J., An identity for Randić’s connectivity index and its applications, ACH Models Chem., 137, 653-658 (2000) |
| [7] | Gutman, I.; Miljković, O.; Caporossi, G.; Hansen, P., Alkanes with small and large Randić connectivity index, Chem. Phys. Lett., 306, 366-372 (1999) |
| [8] | Hansen, P.; Mélot, H., Variable neighborhood search for extremal graphs 6: Analyzing bounds for the connectivity index, J. Chem. Inform. Comput. Sci., 43, 1-14 (2003) |
| [9] | Ivanciuc, O.; Klein, D. J., Building block computation of Wiener-type indices for the virtual screening of combinatorial libraries, Croat. Chim. Acta, 75, 577-601 (2002) |
| [10] | Kier, L. B.; Hall, L. H., Molecular Connectivity in Chemistry and Drug Research (1976), Academic Press: Academic Press New York |
| [11] | Kier, L. B.; Hall, L. H., Molecular Connectivity in Structure-Activity Analysis (1986), Wiley: Wiley New York |
| [12] | Polansky, O. E.; Bonchev, D., The Wiener number of graphs. I. General theory and changes due to some graph operations, MATCH-Commun. Math. Comput. Chem., 21, 133-186 (1986) · Zbl 0603.05045 |
| [13] | Rada, J.; Araujo, O., A recursive formula for the Randić index of a tree, MATCH-Commun. Math. Comput. Chem., 49, 15-21 (2003) · Zbl 1120.05303 |
| [14] | Randić, M., On characterization of molecular branching, J. Amer. Chem. Soc., 97, 6609-6615 (1975) |
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.
