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

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.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/05 - Analisi Matematica
English
Con Impact Factor ISI
Coupon collector's problem; Edge cover; Graph
Tauraso, R. (2008). Edge cover time for regular graphs. JOURNAL OF INTEGER SEQUENCES, 11(4).
Tauraso, R
Articolo su rivista
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/27711
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact