A Covering pursuit game

Abstract In the “Covering” pursuit game on a graph, a robber and a set of cops play alternately, with the cops each moving to an adjacent vertex (or not moving) and the robber moving to a vertex at distance at most 2 from his current vertex. The aim of the cops is to ensure that, after every one of their turns, there is a cop at the same vertex as the robber. How few cops are needed? Our main aim in this paper is to consider this problem for the two‐dimensional grid . Bollobás and Leader asked if the number of cops needed is . We answer this question by showing that cops suffice. We also consider some applications. In particular we study the game “Catching a Fast Robber,” concerning the number of cops needed to catch a fast robber of speed on the two‐dimensional grid . We improve the bounds proved by Balister, Bollobás, Narayanan and Shaw for this game.