Random Walks on Regular and Irregular Graphs

Abstract

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 properties. Namely, for any connected graph, the cyclic cover time is $\Theta (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 the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved 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 )$.