Edge Cover Time for Regular Graphs
Dipartimento di Matematica
Università di Roma "Tor Vergata"
via della Ricerca Scientifica
Consider the following stochastic process on a graph: initially all
vertices are uncovered and at each step cover the two vertices of a
random edge. What is the expected number of steps required to cover
all vertices of the graph? In this note we show that the mean cover
time for a regular graph of N vertices is asymptotically
(N log N)/2.
Moreover, we compute the exact mean cover time for some regular
graphs via generating functions.
Full version: pdf,
(Concerned with sequences
Received October 23 2006;
revised version received May 24 2008; September 30 2008.
Published in Journal of Integer Sequences, October 4 2008.
Journal of Integer Sequences home page