The cover time of a random walk on a finite connected graph is the first time by which every
graph vertex has been visited (Aldous 1991). For
a discrete-time random walk that chooses each adjacent
vertex with equal probability, write for this random
variable and
for its largest expectation value over the starting
graph vertex
.
Let be the growing random
recursive tree model in which attachment to a graph
vertex with
children has weight
, where
,
or
for an integer
. For a random walk
started at the root vertex, Angel et al. (2026)
proved that
in probability with respect to both the random tree and the random walk, where
,
is the principal branch
of the Lambert W-function, and
is the natural logarithm.
They also proved
,
with this expectation value taken over the tree. For uniform attachment,
and
.