Albion College
Mathematics and Computer Science
Cops and Robbers on Graphs
Robert W. Bell

Assistant Professor of Mathematics

Department of Mathematics

Michigan State University

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.
3:10 PM
All are welcome!
Palenske 227
February 3, 2011