inria-00482117, version 1
Cop and robber games when the robber can hide and ride
Jérémie Chalopin
1Victor Chepoi
1Nicolas Nisse
2Yann Vaxès
1
8th French Combinatorial Conference (2010)
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 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.
- 1 : Laboratoire d'informatique Fondamentale de Marseille (LIF)
- CNRS : UMR6166 – Université de la Méditerranée - Aix-Marseille II – Université de Provence - Aix-Marseille I
- 2 : MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
- INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- Domaine : Informatique/Mathématique discrète
Mathématiques/Combinatoire
- inria-00482117, version 1
- http://hal.inria.fr/inria-00482117
- oai:hal.inria.fr:inria-00482117
- Contributeur : Nicolas Nisse
- Soumis le : Dimanche 9 Mai 2010, 00:30:57
- Dernière modification le : Dimanche 9 Mai 2010, 20:27:52






Documents associés
Exporter