Help! A Robber's on the Loose!

A robber is trying to escape and we need to stop them! They are getting away by zig zagging through the streets of Riverside. Cops are scattered throughout the city placed at different street intersections. When the robber moves one block, each cop is able to move one block. How many cops would we need to guarantee that the robber is caught and thrown into jail?

Of course if we positioned a cop at EVERY intersection, then we would

definitely catch the robber. But we have a budget, and if we want to save money, we would want the smallest number of cops needed to catch any robber. We can also change the rules to say that only one cop is able to move on any turn and the others are deemed “lazy” cops, i.e. they stay put on every turn. What is the minimum number of cops needed to catch the robber then?

The scenario described above is a pursuit-evasion game that is played on a

graph, which is called Cops and Robbers. It was first introduced independently by Quilliot in 1978 and Nowakowski and Winkler in 1983. For a graph G, we will investigate the minimum number of cops required to guarantee a winning strategy to catch the robber both in the original and lazy version. With the lazy version, the game takes on the spirit of chess since only one cop moves and this will motivate the types of graphs we will explore.