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.
Tauraso, R. (2008). Edge cover time for regular graphs. JOURNAL OF INTEGER SEQUENCES, 11(4).
Edge cover time for regular graphs
TAURASO, ROBERTO
2008-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
