The following papers give bounds on the cover time. The bounds are expressed
as functions of the number of vertices in the graph, and are best possible
up to low order terms.
A Tight Upper Bound on the Cover Time for Random Walks on Graphs.
Random Structures and Algorithms, 6(1), 51--54, 1995.
A Tight Lower Bound on the Cover Time for Random Walks on Graphs.
Random Structures and Algorithms, 6(4), 433--438, 1995.
The following paper
(with Don Coppersmith and James Shearer)
shows upper bounds that are expressed as a function of the
"virtual resistance" of a graph, a parameter that measures the regularity
of the graph. The more regular a graph is, the better the bounds.
Random Walks on Regular and Irregular Graphs.
SIAM Journal on Discrete Mathematics, 9(2), 301--308, 1996.
The following paper refines the spanning tree argument and obtains stronger
upper bounds on the cover time. Among other things, it is proved
that the path is the tree with highest cover time.
Collecting Coupons on Trees, and the Analysis of Random Walks.
Computational Complexity 6 (1996/1997), 341--356.
The following papers (first with Yuri Rabinovich, second with improved analysis with Eden Chlamtac)
give a deterministic polynomial
time algorithm that approximates the cover time within polylogarithmic
factors. The algorithms works regardless of the starting point of the
random walk, and extends to arbitrary reversible Markov chains.
Deterministic Approximation of the Cover Time.
Random Structures and Algorithms, 23(1), 1--22, 2003.
Improved Approximation of the Minimum Cover Time.
Theor. Comput. Sci. 341(1-3): 22-38 (2005).
The following paper (together with Ofer Zeitouni) presents a deterministic algorithm
that approximates the cover time of trees to any desired degree of accuracy,
though the running time deteriorates the higher the accuracy required.
Deterministic Approximation for the Cover Time of Trees.
In arxiv.org, September 2009.
The following papers (the first of which is with Greg Barnes)
contain results on the rate at which
a random walk discovers previously unvisited vertices (the short term
behavior of random walks), and use them to obtain better time-space
tradeoffs for randomized s-t connectivity algorithms.
The second of these papers introduced the notion of virtual resistance,
mentioned above.
Short Random Walks on Graphs.
SIAM Journal on Discrete Mathematics, 9(1), 19--28, 1996.
A Spectrum of Time-Space Tradeoffs for Undirected s-t Connectivity.
Journal of Computer and System Sciences, 54(2), 305--316, 1997.
The following paper shows a randomized space-efficient algorithm that
determines whether a graph is connected.
The naive approach is to perform a sufficiently long random walk and
check whether all vertices are visited. However, it is difficult to implement
this approach in logarithmic space (without making the walk unnecessarily
long), because there is insufficient space to record which vertices have
been visited. Instead, the method used is based on using random walks to
estimate the size of connected components.
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.
Theoretical Computer Science 169, 147--160, 1996.
The following paper (with Roee David) considers random walks in which each edge of the graph has resistance equal to the minimum degree of its endpoints, and at any given vertex, the walk chooses an outgoing edge with probability inversely proportional to the resistance of the the edge. The main result is a proof of a conjecture of Abdullah, Cooper and Draief [2015] that for every connected graph, the cover time of such walks is at most O(n^2).
Random walks with the minimum degree local rule have O(n^2) cover time
In arxiv.org, April 2016.