MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTECop and robber games when the robber can hide and ride
par Nicolas Nisse
| Date : | 12/01/10 | | Time : | 10:30 | | Location : | Lagrange Gris |
In the classical cop and robber game, two players, the cop and the
robber, move alternatively along edges of a finite graph. 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 (defined by a particular ordering of the vertices). In this
work, we investigate three different variants of cop and robber games:
when the robber is faster, when the robber is visible only every k
moves (k fixed), and when the cop captures the robber in some
neighborhood (when the cop has a "tazzer" :) ). We characterize the
cop-win graphs in several of these games.
This joint work with V. Chepoi, J. Chalopin and Y. Vaxes
Page des séminaires
| 
