This analysis reveals how capture time changes with multiple robbers in cop-win graphs, suggesting significant variations.
The game of cops and robber is a pursuit-evasion game played on graphs that has been extensively studied. Traditionally the game is played with one or more cops and only one robber, but in this paper we consider the game played with multiple robbers, with rules allowing for consecutive capture of the robbers. While the cop number remains the same, the capture time can differ drastically compared to the game played with one robber. In this paper we present general upper bounds for the capture time of cop-win graphs in the game with multiple robbers and show that they are the best possible for some families of graphs. Moreover, we explore how the capture time behaves with an increasing number of robbers and prove a surprising relation between this behavior and the 0-visibility cop number.
No takes yet. Share an insight, caveat, or question.
Gyergyek et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: