Cops and Robbers on Geometric Graphs
Published in Combinatorics, Probability and Computing, 2012
A. Beveridge, A. Dudek, A. Frieze, T. Müller, Cops and Robbers on Geometric Graphs, Combinatorics, Probability and Computing, Vol. 21, No. 6, (2012), pp. 816-834.
Preprint link: https://arxiv.org/abs/1108.2549
Cops and robbers is a turn-based pursuit game played on a graph G.
In each round, one robber and the set of cops move between vertices along the edges of the graph. We show that for any connected random geometric graphs, we need at most 9 cops to catch the robber. We also find bounds on the connectivity radius that guarantee that we need one cop or two cops for these dense graphs.