Cops and Robber - When Capturing is not Surrounding

Abstract

We consider "surrounding" versions of the classic Cops and Robber game. The game is played on a connected graph in which two players, one controlling several cops and the other controlling a single robber, take alternating turns. In a turn, each player may move each of their pieces. The robber always moves between adjacent vertices. Regarding the moves of the cops, we distinguish four versions that differ in whether the cops are on the vertices or the edges of the graph and whether the robber may move on/through them. The goal of the cops is to surround the robber, i.e., to occupy all neighbors (vertex version) or incident edges (edge version) of the robber's current vertex. In contrast, the robber tries to avoid being surrounded indefinitely. Given a graph, the so-called cop number denotes the minimum number of cops required to eventually surround the robber.

We relate the different cop numbers of these versions by showing that they are always within a factor of two times the maximum degree of one another. Furthermore, we prove that none of them is bounded by a function of the classical cop number and the maximum degree of the graph, thereby refuting a conjecture by Crytser, Komarov and Mackey [Graphs and Combinatorics, 2020].