Far Eastern Mathematical Journal

To content of the issue

Asymptotic normality of the Zagreb index of random b-ary recursive trees

Qunqiang Feng, Zhishui Hu

2015, issue 1, . 91-101

The b-ary recursive trees model is one of simple families of increasing trees. In this work, the Zagreb index Zn of a random b-ary recursive tree of size n is studied. As $n\to\infty$, the asymptotic normality of $Z_n$ is established through the martingale central limit theorem, as well as the asymptotic expressionsof the mean and variance of $Z_n$ are given.

random tree, Zagreb index, martingale, asymptotic normality

Download the article (PDF-file)


[1] V. Andova, S. Bogoev, D. Dimitrov, M. Pilipczuk and R. Skrekovski, "On the Zagreb index inequality of graphs with prescribed vertex degrees", Discrete Applied Mathematics, 159 (2011), 852-858.
[2] F. Bergeron, P. Flajolet and B. Salvy, "Varieties of increasing trees, in: Raoult, J.C. (Ed.), Proc. 17th Coll. Trees in Algebra and Programming (Lecture Notes Comput. Sci.). V. 581, Springer, Berlin, 1992, 24-48.
[3] N. Broutin, L. Devroye, E. McLeish and M. de la Salle, "The height of increasing trees", Random Structures and Algorithms, 32 (2008), 494-518.
[4] Q. Feng and Z. Hu, "On the Zagreb index of random recursive trees", Journal of Applied Probability, 48 (2011), 1189-1196.
[5] I. Gutman and N. Trinajsti'c, "Graph theory and molecular orbitals. Total $\phi$-electron energy of alternant hydrocarbons", Chemical Physics Letters, 17 (1972), 535-538.
[6] P. Hall and C. C. Heyde, Martingale limit theory and its application, Academic Press, New York, 1980.
[7] S. Janson, "Random cutting and records in deterministic and random trees", Random Structures and Algorithms, 29 (2006), 139-179.
[8] D. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searchingn, ed. 2nd, Addison-Wesley, Reading, Massachusetts, 1998. Asymptotic normality of the Zagreb index of random b-ary recursive trees 101.
[9] M. Kuba and A. Panholzer, "On the degree distribution of the nodes in increasing trees", Journal of Combinatorial Theory, Series A, 114 (2007), 597-618.
[10] S. Nikoli'c, G. Kova cevi c, A. Mili cevi c and N. Trinajsti'c, "The Zagreb indices 30 years after", Croatica Chemica ACTA, 76 (2003), 113-124.
[11] A. Panholzer and H. Prodinger, "The level of nodes in increasing trees revisited", Random Structures and Algorithms, 31 (2007), 203-226.

To content of the issue