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. |