The weak cop number of a graph
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.