A note on the last new vertex visited by a random walk |
| |
Authors: | L szlo Lov sz,Peter Winkler |
| |
Affiliation: | Lászlo Lovász,Peter Winkler |
| |
Abstract: | 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 Cn 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 Kn 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. |
| |
Keywords: | |
|
|