Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G , let T G (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 T G (x, y) is maximized. the extremal graph consists of a clique on ⌊(2 n + 1)/3⌋) (or ⌈)(2 n − 2)/3⌉) vertices, including x , to which a path on the remaining vertices, ending in y , has been attached; the expected time T G (x, y) to reach y from x in this graph is approximately 4 n 3 /27.