This article is cited in 1 paper

Theory of Probability and Mathematical Statistics

Number of maximal rooted trees in uniform attachment model via stochastic approximation

Yu. A. Malyshkin<sup>ab

a</sup> Tver State University, Tver
^b Moscow Institute of Physics and Technology, Moscow

Abstract: We study the asymptotic behavior of the number of maximal trees in a uniform attachment model. In our model, we consider a sequence of graphs built by the following recursive rule. We start with the complete graph on $m+1$ vertices, $m>1$. Then on the $n+1$ step, we add vertex $n+1$ and draw $m$ edges from it to different vertices, chosen uniformly from $1,\ldots,n$. We prove the convergence speed for the number of maximal trees in such a model using the stochastic approximation technique.

Keywords: random graphs, uniform attachment, stochastic approximation.

UDC: 519.17, 519.21

MSC: 05C80

Received: 08.08.2022
Revised: 30.08.2022

DOI: 10.26456/vtpmk640

Bibliographic databases:

• 
•