Premium
A note on the last new vertex visited by a random walk
Author(s) -
Lovász Lászlo,
Winkler Peter
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170505
Subject(s) - combinatorics , vertex (graph theory) , mathematics , vertex cover , graph , random walk , discrete mathematics , statistics
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.