Random walks with the minimum degree local rule have $O(n^2)$ cover time

Roee David, Uriel Feige

For a simple (unbiased) random walk on a connected graph with $n$ vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most $O(n^3)$. We con…