Дальневосточный математический журнал

К содержанию выпуска


Асимптотическая нормальность загребского индекса случайных b-арных рекурсивных деревьев


Фэн К., Ху З.

2015, выпуск 1, С. 91-101


Аннотация
Модель b-арных рекурсивных деревьев является одним из простыхсемейств растущих деревьев. В данной работе изучается загребскийиндекс Zn случайного b-арного дерева размера n. При $n\to\infty$асимптотическая нормальность $Z_n$ устанавливается из центральной предельной теоремы о мартингалах. Вместе с этим получаютсяасимптотические выражения среднего значения и дисперсии $Z_n$.

Ключевые слова:
случайное дерево, загребский индекс, мартингал, асимптотическая нормальность

Полный текст статьи (файл PDF)

Библиографический список

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

К содержанию выпуска