ASYMPTOTIC BEHAVIOUR OF THE COMPLEXITY INDEX OF GROWING RANDOM TREES
DOI:
https://doi.org/10.15407/dopovidi2024.03.003Keywords:
random tree, recursive tree, coalescent random forest, Wiener index, graph complexityAbstract
In the article a definition of the complexity index of a growing random acyclic graph is proposed. This value can be considered as a modification of the Wiener index, which was introduced as a measure of compactness of a molecular graph and is defined as the sum of distances between all pairs of vertices of the graph. Like the Wiener index, the proposed complexity index characterizes the shape or sparsity of a graph, but can be computed not only for a connected graph but also for a random forest. Its multiplicative property allowed us to estimate from below the mathematical expectation of the complexity index of the random tree resulting from the merging of random forests. For the recursive uniform random tree the asymptotic behaviour of both the mathematical expectation of the complexity index and the complexity index itself are established. The proposed measure of complexity can be applied to a wide class of random graphs with markovian growth dynamics.
Downloads
References
Wiener, H. (1947). Structural determination of paraffin boiling points. J. the Amer. Chem. Society, 69, No. 1, pp.17-20.
Diudea, M. V. & Gutman, I. (1998). Wiener-type topological indeces. Croatica Chem. Acta, 71, № 1, pp. 21-51.
Dobrynin, A. A., Entringer, R. & Gutman, I. (2001). Wiener index of trees: theory and application. Acta Appl. Math., 66, pp. 211-249. https://doi.org/10.1023/A:1010767517079
Rada, J. (2005). Variation of the Wiener index under tree transformation. Discrete Appl. Math., 148, pp. 135–146. https://doi.org/101016/j.dam2004.07.008
Neininger, R. (2002). The Wiener index of random trees. Combinatorics, Probability and Computing, 11, No. 6, pp. 587-597.
Smythe, R. & Mahmoud, H. (1995). A survey of recursive trees. Theory Probab. Math. Statist., 51, pp. 1-27.
Janson, S. (2003). The Wiener index of simply generated random trees. Random structures and algorithms., 22, Iss. 4, pp. 337-358. https://doi.org/10.1002/rsa.10074
Aldous, D. (1991). The continuum random tree I. The Annals of Probability, 19, Iss. 1, pp. 1-28. https://doi.org/10.1214/aop/1176990534
Pitman, J. (1999). Coalescent Random Forests. J. Combinatorial Theory, A85, pp. 165-193. https://doi.org/10.1006/jcta.1998.2919
Aldous, D. J. (1990). A random tree model associated with random graphs. Random Structures and Algorithms, 1, Iss. 4, p. 383-402. https://doi.org/10.1002/rsa.324001042
Buffet, E. & Pulé, J. V. (1991). Polymers and random graphs. J. Statist. Phys., 64, pp. 87-110. https://doi.org/10.1007/BF01057869
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
