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 dismantlable graphs. In this talk, we will 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 (which we call k-winnable and denote by CWW(k)) 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 k-winnable for any value of k.
Type de document :
Communication dans un congrès
8th French Combinatorial Conference, Jun 2010, Orsay, France. 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00482117
Contributeur : Nicolas Nisse <>
Soumis le : dimanche 9 mai 2010 - 00:30:57
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : vendredi 19 octobre 2012 - 14:35:43

Fichier

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

Identifiants

  • HAL Id : inria-00482117, version 1

Citation

Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, Yann Vaxès. Cop and robber games when the robber can hide and ride. 8th French Combinatorial Conference, Jun 2010, Orsay, France. 2010. 〈inria-00482117〉

Partager

Métriques

Consultations de la notice

512

Téléchargements de fichiers

85