View an n-vertex, m-edge undirected graph as an electrical network wit
h unit resistors as edges. We extend known relations between random wa
lks and electrical networks by showing that resistance in this network
is intimately connected with the lengths of random walks on the graph
. For example, the commute time between two vertices s and t (the expe
cted length of a random walk from s to t and back) is precisely charac
terized by the effective resistance R-st between s and t: commute time
= 2mR(st). As a corollary, the cover time (the expected length of a r
andom walk visiting all vertices) is characterized by the maximum resi
stance R in the graph to within a factor of log n: mR less than or equ
al to cover time less than or equal to O(mR log n). For many graphs, t
he bounds on cover time obtained in this manner are better than those
obtained from previous techniques such as the eigenvalues of the adjac
ency matrix. In particular, we improve known bounds on cover times for
high-degree graphs and expanders, and give new proofs of known result
s for multidimensional meshes. Moreover, resistance seems to provide a
n intuitively appealing and tractable approach to these problems.