Abstract

The game of cops and robbers is played on a fixed graph G. The cop picks a vertex to start at, and the robber then does the same. Then they move alternately, with the cop moving first: at each turn the player moves to an adjacent vertex or does not move. The game is won by the cop if he lands on the robber. The graph G is called cop-win if the cop has a winning strategy, and weak cop-win if the cop has a strategy that ensures that the robber is either caught or visits each vertex only finitely many times.

How can we characterise the graphs on which we can, if we are smart enough, catch the robber? On a finite graph, we know the answer exactly. These are called `constructible’ graphs: obtained recursively from the one-point graph by repeatedly adding dominated vertices.

What about infinite graphs? This notion totally fails to describe the cop-win graphs.

In this talk we investigate the relation between constructible graphs and cop-win or weak cop-win graphs. We also investigate how these notions relate to the (weaker and more natural) notion of ‘locally constructible’ (every finite subgraph is contained in a finite constructible subgraph). It turns out that we can have exotic examples, locally constructible, on which the robber can outsmart the robber.