Albion College Mathematics and Computer Science Colloquium



Title: Cops and Robbers on Graphs
Speaker:Robert W. Bell
Assistant Professor of Mathematics
Department of Mathematics
Michigan State University
East Lansing, MI
Abstract: 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.
Location: Palenske 227
Date:2/3/2011
Time: 3:10 PM



@abstract{MCS:Colloquium:RobertWBell:2011:2:3,
author  = "{Robert W. Bell}",
title   = "{Cops and Robbers on Graphs}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month   = "{3 March}",
year    = "{2011}"
}