No Detail Found!

On the last new vertex visited by a random walk in a directed graph

Author(s)
Calum Buchanan Department of Mathematics and Statistics, University of Vermont,Burlington, VT,USA
Paul Horn Department of Mathematics, University of Denver,Denver, CO,USA
Puck Rombach Department of Mathematics and Statistics, University of Vermont,Burlington, VT,USA
Abstract
Consider a simple graph in which a random walk begins at a given vertex. It moves at each step with equal probability to any neighbor of its current vertex, and ends when it has visited every vertex. We call such a random walk a random cover tour. It is well known that cycles and complete graphs have the property that a random cover tour starting at any vertex is equally likely to end at any other vertex. Ronald Graham asked whether there are any other graphs with this property. L a´szlo Lova´ sz and Peter Winkler showed that cycles and complete graphs are the only undirected graphs with this property. We strengthen this result by showing that cycles and complete graphs (with all edges considered bidirected) are the only directed graphs with this property.
Publication Details
Page(s) 96-98
Published Journal: Discrete Mathematics Letters, Volume: 11, Issue: 0, Year: 2023

Request the full text from PASTIC

Keywords
cover tours, random walks, directed graphs
0

Citations

0

Downloads

68

Views