Journal of Integer Sequences, Vol. 11 (2008), Article 08.4.4

Edge Cover Time for Regular Graphs

Roberto Tauraso
Dipartimento di Matematica
Università di Roma "Tor Vergata"
via della Ricerca Scientifica
00133 Roma


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