On the Zagreb index of random recursive trees. (English) Zbl 1234.05053

Summary: We investigate the Zagreb index, one of the topological indices, of random recursive trees in this paper. Through a recurrence equation, the first two moments of \(Z_{n}\), the Zagreb index of a random recursive tree of size \(n\), are obtained. We also show that the random process \({Z_{n} - E[Z_{n}], n \geq 1}\) is a martingale. Then the asymptotic normality of the Zagreb index of a random recursive tree is given by an application of the martingale central limit theorem. Finally, two other topological indices are also discussed in passing.


05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
Full Text: DOI


[1] Ali Khan, T. and Neininger, R. (2007). Tail bounds for the Wiener index of random trees. In 2007 Conference on Analysis of Algorithms, AofA 07 (Discrete Math. Theoret. Comput. Sci. Proc. AH ), Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 279-289. · Zbl 1192.68198
[2] Barysz, M., Plavšić, D. and Trinajstić, N. (1986). A note on topological indices. MATCH Commun. Math. Comput. Chem. 19 , 89-116. · Zbl 0585.05035
[3] Clark, L. H. and Moon, J. W. (2000). On the general Randić index for certain families of trees. Ars Combinatoria 54 , 223-235. · Zbl 0991.92040
[4] Devillersand. J. and Balaban, A. T. (1999). Topological Indices and Related Descriptors in QSAR and QSPR . Gordon and Breach, Amsterdam.
[5] Devroye, L. and Lu, J. (1995). The strong convergence of maximal degrees in uniform random recursive trees and dags. Random Structures Algorithms 7 , 1-14. · Zbl 0835.05062
[6] Feng, Q. (2011). The Zagreb index of random binary trees. Unpublished manuscript. · Zbl 1234.05053
[7] Feng, Q., Mahmoud, H. M. and Panholzer, A. (2008). Limit laws for the Randić index of random binary tree models. Ann. Inst. Statist. Math. 60 , 319-343. · Zbl 1332.68038
[8] Goh, W. and Schmutz, E. (2002). Limit distribution for the maximum degree of a random recursive tree. J. Comput. Appl. Math. 142 , 61-82. · Zbl 1003.05093
[9] Gordon, M. and Scantlebury, G. R. (1964). Non-random polycondensation: statistical theory of the substitution effect. Trans. Faraday Soc. 60 , 604-621.
[10] Gutman, I. and Trinajstić, N. (1972). Graph theory and molecular orbitals. Total \(\varphi\)-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 17 , 535-538.
[11] Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application . Academic Press, New York. · Zbl 0462.60045
[12] Harary, F. (1972). Graph Theory. Addison-Wesley, Reading, MA. · Zbl 0235.05105
[13] Hollas, B. (2005). Asymptotically independent topological indices on random trees. J. Math. Chem. 38 , 379-387. · Zbl 1217.05207
[14] Janson, S. (2003). The Wiener index of simply generated random trees. Random Structures Algorithms 22 , 337-358. · Zbl 1025.05021
[15] Janson, S. and Chassaing, P. (2004). The center of mass of the ISE and the Wiener index of trees. Electron. Commun. Prob. 9 , 178-187. · Zbl 1060.60095
[16] Li, X., Li, Z. and Wang, L. (2003). The inverse problems for some topological indices in combinatorial chemistry. J. Comput. Biol. 10 , 47-55.
[17] Neininger, R. (2002). The Wiener index of random trees. Combinatorics Prob. Comput. 11 , 587-597. · Zbl 1013.05029
[18] Nikolić, S., Kovačević, G., Miličević, A. and Trinajstić, N. (2003a). The Zagreb indices 30 years after. Croatica Chemica Acta 76 , 113-124.
[19] Nikolić, S., Tolić, I. M., Trinajstić, N. and Baučić, I. (2000). On the Zagreb indices as complexity indices. Croatica Chemica Acta 73 , 909-921.
[20] Nikolić, S. \et (2003b). On molecular complexity indices. In Complexity in Chemistry: Introduction and Fundamentals , eds D. Bonchev and D. H. Rouvray, Taylor and Francis, London, pp. 29-89.
[21] Platt, J. R. (1947). Influence of neighbor bonds on additive bond properties in paraffins. J. Chem. Phys. 15 , 419-420.
[22] Smythe, R. T. and Mahmoud, H. M. (1994). A survey of recursive trees. Teor. Imovir. Mat. Stat. 51 , 1-29 (in Ukrainian). English translation: Theory Prob. Math. Statist. 51 (1996), 1-27. · Zbl 0933.05038
[23] Trinajstić, N. (1992). Chemical Graph Theory , 2nd edn. CRC Press, Boca Raton, FL.
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.