Bounds on the cover time

Consider a particle that moves on a connected, undirected graphG withn vertices. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. Tocover 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 (n logn).This research was done while this author was a postdoctoral fellow in the Department of Computer Science, Princeton University, and it was supported in part by DNR grant N00014-87-K-0467.