×

On a nonuniform random recursive tree. (English) Zbl 0646.05023

Random graphs ’85, Lect. 2nd Int. Semin., Poznań/Pol. 1985, Ann. Discrete Math. 33, 297-306 (1987).
[For the entire collection see Zbl 0626.00008.]
A tree with n vertices labelled 1,2,...,n is a recursive tree if for each k, \(2\leq k\leq n\), the labels of vertices in the unique path from the first vertex to the kth vertex form an increasing subsequence of integers. In this paper the author deals with random recursive trees for which the probability of joining a new vertex to vertex i depends only on the degree of vertex i. The author obtains a formula for the expected value of the number of vertices of degree k in an n-vertex random recursive tree under various probabilities for a vertex to have degree d.
Reviewer: A.Tucker

MSC:

05C05 Trees
05C80 Random graphs (graph-theoretic aspects)

Citations:

Zbl 0626.00008