Document Type
Lecture
Publication Date
11-14-2014
Abstract
In 2012 Seager introduced a new variant of the Cops and Robbers game, in which a cop searches for a moving robber on a graph using distance probes. The robber on his turn can either remain still or move to an adjacent vertex, while the cop on her turn probes any vertex and learns the robbers distance from the probed vertex. The game ends if after some probe the cop knows the robbers location exactly, in which case she wins. If the robber can always ensure some ambiguity in his position then the game continues forever, in which case we say the robber wins. Some basic results about a graph being cop-win or robber-win are known, but in general the question of classifying graphs remains open. Carraher, Choi, Delcourt, Erickson and West later showed that for any xed graph G there is a winning strategy for the cop on the graph G1 m , obtained by replacing each edge of G by a path of length m, if m is su ciently large. They conjectured that the cop does not have a winning strategy on K1 m n if m < n; we show that in fact the cop wins if and only if m > n2, for all but a few small values of n. We also give a complete answer to the question of when the cop has a winning strategy on K1 m ab . If time permits we may also comment on recently developments in this approach for innite graphs. This is joint work with John Haslegrave in University of She eld and Sebastian Koch at University of Cambridge.
Relational Format
presentation
Recommended Citation
Johnson, Richard, "The Robber Locating Game" (2014). Combinatorics Seminar. 45.
https://egrove.olemiss.edu/math_combinatorics/45
