RANDOM-WALKS ON REGULAR AND IRREGULAR GRAPHS

For an undirected graph and an optimal cyclic list of all its vertices , the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy-to-compute graph pro perties. Namely, for any connected graph, the cyclic cover time is -(n (2)d(ave)(d(-1))(ave)), where n is the number of vertices in the graph , d(ave) is the average degree of its vertices, and (d(-1))(ave) is th e average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar ch aracterization of minimum resistance spanning trees of graphs, improve d bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most 4n(3)/27 + o(n( 3)).