A note on the last new vertex visited by a random walk

A “cover tour” of a connected graph G from a vertex x is a random walk that begins at x, moves at each step with equal probability to any neighbor of its current vertex, and ends when it has hit every vertex of G. The cycle C_n is well known to have the curious property that a cover tour from any vertex is equally likely to end at any other vertex; the complete graph K_n shares this property, trivially, by symmetry. Ronald L. Graham has asked whether there are any other graphs with this property; we show that there are not. © 1993 John Wiley & Sons, Inc.