## Examples & Illusration of the Game:

 Here we give some examples of graphs:

One important thing to notice is that all of the above graphs are finite. In fact all are simple graphs except for #3. Graph #3 is not simple. Also notice that graph #5 is in two "pieces" so it is not connected. With this
game, we will concentrate on connected graphs with only one "piece", that means
graphs 1-4. (Unlike the orignial game of Winkler, the loops or multiple edges do not make a difference in our game.)

Now let us illustrate the cop and robber game. Given a finite simple connected graph,
the cop starts at one vertex, the robber at another. At his turn each must move along
an edge to an adjacent vertex or choose not to move. They alternate turns. The cop tries to land on the
robber (or have the robber land on him!) while, the robber tries to get away.

Now for a questions!
What is the smallest graph (i.e: smallest number of vertices) so that a single robber can always evade a single cop, no matter where they start?

Well, Graph #1 is too small. Graph #5 depends on the starting position. It seems that graph #2 is just right!.
A tree is a special kind of graph. Our graph #4 is an example of a tree. If a graph is a TREE, then the cop will ALWAYS catch the robber.

## Theorem:

A graph is cop-win if and only if the graph is dismantlable.

This leads to an efficient algorithm for this rather complex game!

Describe an algorithm to decide if an input graph is cop-win or robber-win.

If the graph is cop-win, describe an algorithm for the cop to always catch the robber.

## More questions and more cops:

• For a given cop-win graph, what is the number of steps required for the cop to catch the robber (even in the worst case)?

• What happens if we can have more cops?

• The cop number of a graph is defined to be the minimum number of cops needed to catch a robber.
For a given graph, how do we determine its cop number?

References:

1. Richard Nowakawski and Peter Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math 43 (1983), 235-239.
2. Graham Brightwell and Peter Winkler, Gibbs measures and dismantlable graphs, J. Comb. Theory (Series B) 78 (2000), pp. 141-169. PostScript file
3. Bondy and Murty, Graph Theory with Applications, North Holland, 1976.
4. Harary, Graph Theory, Addison-Wesley, 1969.
5. Tero Harju: http://users.utu.fi/harju/exercises.ps.gz
6. H. Jem: http://hjem.get2net.dk/policeshooting/images/div.grafik/
7. M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Math 8 (1984), 1-12. (This paper includes a proof that 3 cops suffice for planar graphs.)