Albion College

Mathematics and Computer Science

Mathematics and Computer Science

COLLOQUIUM

Cops and Robbers on Graphs

Robert W. Bell

Suppose G is a finite graph. Two players play a game on G as follows: one player takes n markers (which
represent "cops") and assigns each one to a vertex of G; then the second player takes one marker (representing
a "robber") and assigns it to a vertex of G. The players then alternate turns, each moving any number of his or
her markers to adjacent vertices each turn. If a cop is moved to the same vertex as the robber, the cop player
wins. If the robber player can always avoid such an outcome the robber player wins. Certainly the cop player can
win on a given graph G if sufficiently many cops are at his disposal. But what is the fewest number of cops needed
to guarantee that the robber can always be captured? This was a topic at a summer Research Experience for
Undergraduates (REU) at Michigan State University in the 2010. The investigations of several of the participants will also be highlighted.