Cops, robbers, and infinite graphs (Seminar DM)

Iz MaFiRaWiki

Cops, robbers, and infinite graphs

Florian Lehner

Torek, 20. januarja 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.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja