If G = (V, E) is a connected, undirected, non-bipartite with n vertices and m edges we can define a Markov chain, MG, on G by defining the transition probability from vertex u to vertex v to be Puv = 1/d(u) when (u,v) is an edge of G and 0 otherwise.

(A graph is bipartite if its vertices can be partitioned into two non-empty sets so that no edge connects vertices within the same set.)

Hitting time
huv = expected time for a random walk starting at u to first reach v

Commute time
Cuv = huv + hvu

Cover time
If Cu(G) is the expected amount of time for a random walk starting at u to visit every vertex of G, the cover time is the maximum of this over all starting vertices


Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995