Skip to Main content Skip to Navigation
New interface
Journal articles

Cop and robber games when the robber can hide and ride

Jérémie Chalopin 1 Victor Chepoi 1 Nicolas Nisse 2 Yann Vaxès 1 
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In the classical cop and robber game, two players, the cop C and the robber 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, Winkler (1983) and Quilliot (1983) characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class CWFR(s, s′) of cop-win graphs in the game in which the cop and the robber move at different speeds s′ and s, s′ ≤ 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′ = 1 and s = 2, we prove that the class of cop-win graphs is exactly the well-known class of dually chordal graphs. We show that all classes CWFR(s, 1), s ≥ 3, 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. We characterize the graphs which are cop-win for any value of k. Finally, we consider the game where the cop wins if he is at distance at most 1 from the robber and we characterize via a specific dismantling scheme the bipartite graphs where a single cop wins in this game.
Document type :
Journal articles
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/inria-00622957
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Tuesday, September 13, 2011 - 10:49:43 AM
Last modification on : Thursday, August 4, 2022 - 4:52:39 PM
Long-term archiving on: : Wednesday, December 14, 2011 - 2:25:36 AM

File

CopRobberFinal2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00622957, version 1

Collections

Citation

Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, Yann Vaxès. Cop and robber games when the robber can hide and ride. SIAM Journal on Discrete Mathematics, 2011, 25 (1), pp.333-359. ⟨inria-00622957⟩

Share

Metrics

Record views

309

Files downloads

108