Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T05:09:13.507Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Zagreb Index of Random Recursive Trees

Part of: Graph theory Limit theorems Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

Qunqiang Feng  and
Zhishui Hu
Qunqiang Feng*
Affiliation:
University of Science and Technology of China
Zhishui Hu*
Affiliation:
University of Science and Technology of China
*
∗ Postal address: Department of Statistics and Finance, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China.
∗ Postal address: Department of Statistics and Finance, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 ≥ 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.

Keywords

Random treeZagreb indexrecursive treemartingale central limit theorem

MSC classification

Secondary: 05C05: Trees 60C05: Combinatorial probability 60F05: Central limit and other weak theorems
Type
Short Communications
Information
Journal of Applied Probability , Volume 48 , Issue 4 , December 2011 , pp. 1189 - 1196
Copyright
Copyright © Applied Probability Trust 2011 

References

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.Google Scholar
Barysz, M., Plavšić, D. and Trinajstić, N. (1986). A note on topological indices. MATCH Commun. Math. Comput. Chem. 19, 89–116.Google Scholar
Clark, L. H. and Moon, J. W. (2000). On the general Randić index for certain families of trees. Ars Combinatoria 54, 223–235.Google Scholar
Devillersand., J. and Balaban, A. T. (1999). Topological Indices and Related Descriptors in QSAR and QSPR. Gordon and Breach, Amsterdam.Google Scholar
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.Google Scholar
Feng, Q. (2011). The Zagreb index of random binary trees. Unpublished manuscript.Google Scholar
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.Google Scholar
Goh, W. and Schmutz, E. (2002). Limit distribution for the maximum degree of a random recursive tree. J. Comput. Appl. Math. 142, 61–82.Google Scholar
Gordon, M. and Scantlebury, G. R. (1964). Non-random polycondensation: statistical theory of the substitution effect. Trans. Faraday Soc. 60, 604–621.Google Scholar
Gutman, I. and Trinajstić, N. (1972). Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 17, 535–538.Google Scholar
Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application. Academic Press, New York.Google Scholar
Harary, F. (1972). Graph Theory. Addison-Wesley, Reading, MA.Google Scholar
Hollas, B. (2005). Asymptotically independent topological indices on random trees. J. Math. Chem. 38, 379–387.Google Scholar
Janson, S. (2003). The Wiener index of simply generated random trees. Random Structures Algorithms 22, 337–358.Google Scholar
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.Google Scholar
Li, X., Li, Z. and Wang, L. (2003). The inverse problems for some topological indices in combinatorial chemistry. J. Comput. Biol. 10, 47–55.Google Scholar
Neininger, R. (2002). The Wiener index of random trees. Combinatorics Prob. Comput. 11, 587–597.Google Scholar
Nikolić, S., Kovačević, G., Miličević, A. and Trinajstić, N. (2003a). The Zagreb indices 30 years after. Croatica Chemica Acta 76, 113–124.Google Scholar
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.Google Scholar
Nikolić, S. et al. (2003b). On molecular complexity indices. In Complexity in Chemistry: Introduction and Fundamentals, eds Bonchev, D. and Rouvray, D. H., Taylor and Francis, London, pp. 29–89.Google Scholar
Platt, J. R. (1947). Influence of neighbor bonds on additive bond properties in paraffins. J. Chem. Phys. 15, 419–420.Google Scholar
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.Google Scholar
Trinajstić, N. (1992). Chemical Graph Theory, 2nd edn. CRC Press, Boca Raton, FL.Google Scholar