Pushing Cops and Robber on Graphs of Maximum Degree 4
By: Harmender Gahlawat
Potential Business Impact:
One cop can catch a robber with special moves.
\textsc{Cops and Robber} is a game played on graphs where a set of \textit{cops} aim to \textit{capture} the position of a single \textit{robber}. The main parameter of interest in this game is the \textit{cop number}, which is the minimum number of cops that are sufficient to guarantee the capture of the robber. In a directed graph $\overrightarrow{G}$, the \textit{push} operation on a vertex $v$ reverses the orientation of all arcs incident on $v$. We consider a variation of classical \textsc{Cops and Robber} on oriented graphs, where in its turn, each cop can either move to an out-neighbor of its current vertex or push some vertex of the graph, whereas, the robber can move to an adjacent vertex in its turn. [Das et al., CALDAM, 2023] introduced this variant and established that if $\overrightarrow{G}$ is an orientation of a subcubic graph, then one cop with push ability has a winning strategy. We extend these results to establish that if $\overrightarrow{G}$ is an orientation of a $3$-degenerate graph, or of a graph with maximum degree $4$, then one cop with push ability has a winning strategy.
Similar Papers
Cops and Robbers for Graphs on Surfaces with Crossings
Discrete Mathematics
Makes it easier to catch a robber in a game.
Cops and Robbers, Clique Covers, and Induced Cycles
Combinatorics
Finds how many cops catch a robber on a map.
Fast and Furious: A study on Monotonicity and Speed in Cops-and-Robber Games
Discrete Mathematics
Helps map computer networks find hidden problems.