ASYMPTOTIC BEHAVIOUR OF THE COMPLEXITY INDEX OF GROWING RANDOM TREES - Dorogovtsev A.А.; Кalytiuk D.М.; Nishchenko І.І. (Reports of the National Academy of Sciences of Ukraine, 2024)
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.