Maximum hitting time for random walks on graphs
Graham Brightwell, Peter M. Winkler · Random Structures and Algorithms · 1990
Abstract For x and y vertices of a connected graph G, let TG(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n‐vertex graph G and vertices x and y for which TG(x, y) is maximized. the extremal graph consists of a clique on ⌊(2n + 1)/3⌋) (or ⌈)(2n − 2)/3⌉) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time TG(x, y) to reach y from x in this graph is approximately 4n3/27.