Bounds on expected hitting times for a random walk on a connected graph

AbstractIt is known that for a random walk on a connected graph G on N vertices {xl,…,xN} satisfying υ(xi)≤ k for all i [υ(xi) is the valence of xi] , the maximum expected number of steps to get from one vertex to another has a bound of order kN(N−1). We give simple sufficient conditions under which, even though υ(xi= O>(N) for all i, the expected hitting times have bounds of orders N, N32, or N52