Cop and Robber Games When the Robber Can Hide and Ride

Abstract

In the classical cop and robber game, two players, the cop $\mathcal{C}$ and the robber $\mathcal{R}$, move alternatively along edges of a finite graph $G=(V,E)$. The cop captures the robber if both players are on the same vertex at the same moment of time. A graph G is called cop win if the cop always captures the robber after a finite number of steps. Nowakowski and Winkler [Discrete Math., 43 (1983), pp. 235–239] and Quilliot [Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, Thèse de doctorat d'état, Université de Paris VI, Paris, 1983] characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class $\mathcal{CWFR}(s,s')$ of cop-win graphs in the game in which the robber and the cop move at different speeds s and $s'$, $s'\leq s$. We also establish some connections between cop-win graphs for this game with $s'<s$ and Gromov's hyperbolicity. In the particular case $s=2$ and $s'=1$, we prove that the class of cop-win graphs is exactly the well-known class of dually chordal graphs. We show that all classes $\mathcal{CWFR}(s,1)$, $s\geq3$, coincide, and we provide a structural characterization of these graphs. We also investigate several dismantling schemes necessary or sufficient for the cop-win graphs in the game in which the robber is visible only every k moves for a fixed integer $k>1$. In particular, we characterize the graphs which are cop-win for any value of k.