Albion College
Mathematics and Computer Science
The weak cop number of a graph
Robert Bell

The weak cop number of an infinite graph

Lyman Briggs College & Department of Mathematics

Michigan State University

The cop number of a finite graph G is defined as the minimal number of cops a player needs to capture an opponent's robber in a game of cops and robbers on G. In this game, the cop player places each of her cop pawns on vertices of G; and then the opponent places his robber pawn on a vertex of G. Both players have complete information about G and the location of the pawns. The players alternate turns, with the cop player playing first, by moving any number of his or her pawns along edges of G to adjacent vertices. If a cop is moved to the same vertex as the robber, then the robber is captured. In this talk, we explore the notion of a weak cop number due to Florian Lehner. Suppose G is a possibly infinite graph. The weak cop number of G is the minimal number of cops needed to either capture the robber or prevent the robber from visiting any vertex of G infinitely often. We compute the weak cop numbers of several families of infinite graphs, extend several theorems to this new setting, and give examples of how some of the foundational theorems for finite graphs fail to extend to infinite graphs. In particular, we will outline how one can bound the weak cop number of a connected, countable, locally finite planar graph. This is joint work with undergraduate participants in the 2015 summer REU program at MSU.
3:30 PM
All are welcome!
Palenske 227
October 29, 2015