Geodesic
Edge cover time for regular graphs
Journal of integer sequences, Tome 11 (2008) no. 4
Zbl   EuDML
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.
Classification : 60C05
Keywords: coupon collector's problem, graph, edge cover 
Tauraso,  Roberto. Edge cover time for regular graphs. Journal of integer sequences, Tome 11 (2008) no. 4. http://geodesic.mathdoc.fr/item/JIS_2008__11_4_a0/
@article{JIS_2008__11_4_a0,
     author = {Tauraso,  Roberto},
     title = {Edge cover time for regular graphs},
     journal = {Journal of integer sequences},
     year = {2008},
     volume = {11},
     number = {4},
     zbl = {1152.05369},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2008__11_4_a0/}
}
TY  - JOUR
AU  - Tauraso,  Roberto
TI  - Edge cover time for regular graphs
JO  - Journal of integer sequences
PY  - 2008
VL  - 11
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/JIS_2008__11_4_a0/
LA  - en
ID  - JIS_2008__11_4_a0
ER  - 
%0 Journal Article
%A Tauraso,  Roberto
%T Edge cover time for regular graphs
%J Journal of integer sequences
%D 2008
%V 11
%N 4
%U http://geodesic.mathdoc.fr/item/JIS_2008__11_4_a0/
%G en
%F JIS_2008__11_4_a0