Combinatorics Seminar -- Torsten Ueckerdt (Karlsruher Institut für Technologie)

16:15-18:00

Speaker: Torsten Ueckerdt (Karlsruher Institut für Technologie)

Title: When Surrounding is not Catching in Cops and Robber

Abstract: 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.