MASCOTTE no longer exists => visit the new COATI project-team
 


Internship MASCOTTE
Some Variants of Cop and Robber games

by Dinh Khanh DANG

 
Advisor Nicolas Nisse
School master IFI parcours UBINET, UNS
Degree master 2
Period 01/03/11-31/08/11
ReportAvailable in pdf

 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 instance. 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. Chalopin et al. characterized the cop-win graphs in the game in which the cop and the robber move at different speeds s'and s, s' < s. Chalopin et al. also charaterized the bipartite graphs in the radius caputre variant in which the cop can capture the robber if their distance is not greater than one. Inheritting from the previous works, we investigate further two variants of cops and robber game, the faster robber and radius capture variants in some particular graphs such as square grid, k-chordal, planar, etc.

List of interships