
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].
ddc:004, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), DATA processing & computer science, 004, containment, pursuit games, FOS: Mathematics, Mathematics - Combinatorics, Combinatorial games, Combinatorics (math.CO), cop number, info:eu-repo/classification/ddc/004, Positional games (pursuit and evasion, etc.), Computer Science - Discrete Mathematics
ddc:004, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), DATA processing & computer science, 004, containment, pursuit games, FOS: Mathematics, Mathematics - Combinatorics, Combinatorial games, Combinatorics (math.CO), cop number, info:eu-repo/classification/ddc/004, Positional games (pursuit and evasion, etc.), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
