Geodesic
Edge cover time for regular graphs
Journal of integer sequences, Tome 11 (2008) no. 4.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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 
@article{JIS_2008__11_4_a0,
     author = {Tauraso, Roberto},
     title = {Edge cover time for regular graphs},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {11},
     number = {4},
     year = {2008},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2008__11_4_a0/
%G en
%F JIS_2008__11_4_a0
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/