HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Monday, January 25, 2010 - 6:01:20 PM
Last modification on : Friday, February 4, 2022 - 3:20:08 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

318

Files downloads

254