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 , 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (1), pp.333-359
Liste complète des métadonnées

https://hal.inria.fr/inria-00622957
Contributeur : Nicolas Nisse <>
Soumis le : mardi 13 septembre 2011 - 10:49:43
Dernière modification le : mercredi 14 décembre 2016 - 01:03:24
Document(s) archivé(s) le : mercredi 14 décembre 2011 - 02:25:36

Fichier

CopRobberFinal2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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, Society for Industrial and Applied Mathematics, 2011, 25 (1), pp.333-359. <inria-00622957>

Partager

Métriques

Consultations de
la notice

417

Téléchargements du document

67