Szymański, Jerzy 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 Cited in 25 Documents MSC: 05C05 Trees 05C80 Random graphs (graph-theoretic aspects) Keywords:recursive tree; random recursive trees Citations:Zbl 0626.00008 PDFBibTeX XML