Height of a random tree. (English) Zbl 0964.05056
The author considers continuous time Markov chains in which the states are finite trees. For each vertex present in the tree, a new edge is attached to the vertex with rate \(\lambda> 0\) and edges are contracted with rate \(\mu\geq 0\). The author shows, among other things, that if \(\mu= 0\) the growth of the expected height of the tree is asymptotically linear; if \(\mu>\lambda\) the process is ergodic; and if \(0< \mu<\lambda\) the growth of the expected height is less than linear but “sufficiently close to linear”.
Reviewer: J.W.Moon (Edmonton)
MSC:
05C80 | Random graphs (graph-theoretic aspects) |
05C05 | Trees |
60B99 | Probability theory on algebraic and topological structures |
05C12 | Distance in graphs |