When Surrounding is not Catching in Cops and Robber

After a short introduction of the classical game of Cops and Robber on graphs, we shall discuss two recently introduced variants in which the robber only loses when he is completely surrounded by the cops. In the first variant the robber is surrounded when he sits at a vertex v and there is at least one cop on each neighbor of v. In the second variant cops occupy edges of the graph and the robber (still moving on vertices) is surrounded if he sits at a vertex v and there is at least one cop on each incident edge at v. We shall compare these games with each other and also with the classical game in which the robber is already caught when one cop sits on the same vertex as the robber.

This is joint work with Paul Jungeblut, Minh Tuan Ha and Samuel Schneider.