FAR EASTERN BRANCH OF THE RUSSIAN ACADEMY OF SCIENCES
INSTITUTE OF APPLIED MATHEMATICS KHABAROVSK DIVISION
Far Eastern Mathematical Journal
Asymptotic normality of the Zagreb index of random b-ary recursive trees |
Qunqiang Feng, Zhishui Hu |
2015, issue 1, P. 91-101 |
Abstract |
| 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. |
Keywords: random tree, Zagreb index, martingale, asymptotic normality |
Download the article (PDF-file) |
References |
| [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. |