SRC Research Report 32
SRC Research Report 32
Consider a particle that moves on a connected, undirected graph G with n vertices. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. The cover time is the first time when the particle has visited all the vertices in the graph starting from a given vertex.
In this paper, we present upper and lower bounds that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the random walk above. An interesting consequence is that regular expander graphs have expected cover time Theta(n ln n).
Back to the SRC Research Reports main page.