A random recursive tree on vertices 1, 2, ..., is a random rooted
tree with root vertex 1 obtained by attaching
each new graph vertex
to a uniformly selected earlier graph
vertex. Equivalently, it is uniformly distributed over rooted
trees whose labels increase along every path away from
the root vertex (Pittel 1994). This distribution differs
from the uniform distribution on all labeled
trees.
More generally, attachment to a graph vertex with
children may have weight
. This rule is defined for
all positive integers
when
, or when
for a positive integer
. For
, the latter rule permits
at most
children per graph vertex. The case
produces a path graph. For
or
with
, the cover time
of a random walk on these growing trees
has an explicit asymptotic constant depending on
(Angel et al. 2026).