##
**
Edge Cover Time for Regular Graphs
**

###
Roberto Tauraso

Dipartimento di Matematica

Università di Roma "Tor Vergata"

via della Ricerca Scientifica

00133 Roma

Italy

**Abstract:**

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,
dvi,
ps,
latex
**

(Concerned with sequences
A000032
A006129
A048291
A054548
A055599
A113214 and
A123304
.)

Received October 23 2006;
revised version received May 24 2008; September 30 2008.
Published in *Journal of Integer Sequences*, October 4 2008.

Return to
**Journal of Integer Sequences home page**