Florian Lehner: Cops, robbers, and infinite graphs

Datum objave: 12. 1. 2015
Seminar za diskretno matematiko
Torek, 20. 1. 2015, od 10h do 12h, Plemljev seminar, Jadranska 19

Povzetek. Pursuit-evasion based searching, also known as the game of cops and robbers, is a game on a graph between two players, C (the cop) and R (the robber). The rules are as follows: In the first round both C and R choose a starting vertex, in each consecutive round they are allowed to move to a neighboring vertex. The cop wins the game, if after some finite number of steps C and R occupy the same vertex, otherwise the robber wins.

A basic question related to this game is to characterize the class of graphs for which the cop has a winning strategy. For finite graphs it has been shown by Nowakowski and Winkler that these are exactly the constructible graphs.

For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they believed the same to be true. We disprove this conjecture and suggest a further modification in the same spirit for which we can show that the cop has a winning strategy on every constructible graph.