Skip to Main content Skip to Navigation
Reports

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 cop-win graphs in the game in which the cop and the robber move at different speeds s' and s, s'<= s. 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.
Document type :
Reports
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/inria-00448243
Contributor : Nicolas Nisse <>
Submitted on : Monday, January 25, 2010 - 6:01:20 PM
Last modification on : Tuesday, December 8, 2020 - 10:16:36 AM
Long-term archiving on: : Thursday, September 23, 2010 - 6:01:58 PM

File

RR-7178.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00448243, version 3

Citation

Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, Yann Vaxès. Cop and robber games when the robber can hide and ride. [Research Report] RR-7178, INRIA. 2010, pp.44. ⟨inria-00448243v3⟩

Share

Metrics

Record views

819

Files downloads

537