Paper Info
Title
An evasion game on a graph.
Abstract
This paper introduces a pursuit and evasion game to be played on a connected graph. One player moves invisibly around the graph, and the other player must guess his position. At each time step the second player guesses a vertex, winning if it is the current location of the first player; if not the first player must move along an edge. It is shown that the graphs on which the second player can guarantee to win are precisely the trees that do not contain a particular forbidden subgraph, and best possible capture times on such graphs are obtained.
Year
DOI
Venue
2014
10.1016/j.disc.2013.09.004
Discrete Mathematics
Keywords
DocType
Volume
Pursuit game,Evasion game,Tree,Cops and robbers,Graph searching
Journal
314
ISSN
Citations 
PageRank 
0012-365X
7
0.63
References 
Authors
6
1
Name
Order
Citations
PageRank
John Haslegrave1295.74