Portal de Periódicos da CAPES

Cop and Robber Games When the Robber Can Hide and Ride

2011; Society for Industrial and Applied Mathematics; Volume: 25; Issue: 1 Linguagem: Inglês

10.1137/100784035

1095-7146

Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, Yann Vaxès,

Complexity and Algorithms in Graphs

In the classical cop and robber game, two players, the cop $\mathcal{C}$ and the robber $\mathcal{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 and Winkler [Discrete Math., 43 (1983), pp. 235–239] and Quilliot [Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, Thèse de doctorat d'état, Université de Paris VI, Paris, 1983] characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class $\mathcal{CWFR}(s,s')$ of cop-win graphs in the game in which the robber and the cop move at different speeds s and $s'$, $s'\leq s$. We also establish some connections between cop-win graphs for this game with $s' 1$. In particular, we characterize the graphs which are cop-win for any value of k.