Summary: 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. R. Nowakowski and P. Winkler [Discrete Math. 43, 235–239 (1983; Zbl 0508.05058)] and A.Quilliot [Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes. Paris: Université de Paris VI (Dissertation) (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^\prime)\) of cop-win graphs in the game in which the robber and the cop move at different speeds \(s\) and \(s^\prime, s^\prime\leq s\). We also establish some connections between cop-win graphs for this game with \(s^\prime<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\).