Cop and robber games when the robber can hide and ride - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2010

Cop and robber games when the robber can hide and ride

Résumé

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.
Fichier principal
Vignette du fichier
RR-7178.pdf (518.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00448243 , version 1 (18-01-2010)
inria-00448243 , version 2 (25-01-2010)
inria-00448243 , version 3 (25-01-2010)

Identifiants

  • HAL Id : inria-00448243 , version 2

Citer

Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, Yann Vaxès. Cop and robber games when the robber can hide and ride. RR-7178, 2010. ⟨inria-00448243v2⟩
352 Consultations
323 Téléchargements

Partager

Gmail Facebook X LinkedIn More