Cops and robber -- when capturing is not surrounding

Paul Jungeblut¹ ; Samuel Schneider¹ ; Torsten Ueckerdt¹

¹Karlsruhe Institute of Technology

The electronic journal of combinatorics, Tome 32 (2025) no. 3

Résumé

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].

Détail

DOI : 10.37236/13508

Classification : 05C57, 91A43, 91A24, 91A46
Mots-clés : pursuit games, cop number, containment