On the cover time of random walks on graphs
This article deals with random walks on arbitrary graphs. We consider the cover time of finite
graphs. That is, we study the expected time needed for a random walk on a finite graph to
visit every vertex at least once. We establish an upper bound of O (n 2) for the expectation of
the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω (n log n)
for the expected cover time for trees. We present examples showing all our bounds to be
tight.
graphs. That is, we study the expected time needed for a random walk on a finite graph to
visit every vertex at least once. We establish an upper bound of O (n 2) for the expectation of
the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω (n log n)
for the expected cover time for trees. We present examples showing all our bounds to be
tight.
Abstract
This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n 2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.
Springer