Quickly Catching a Robber in a Graph

The game of Cops and Robbers involves a team of cops trying to catch a single robber on a graph \(G\). The players alternate turns moving along edges of \(G\). The speaker will first survey some of the major theorems and conjectures concerning the cop number of graphs, i.e., the minimum number of cops needed to guarantee catching the robber. Then, the speaker will turn to new work (joint with Anthony Bonato, Xavier Pérez-Giménez, and Paweł Prałat) on the minimum number of turns needed for \(k\) cops to catch the robber, called the \(k\)-capture time of \(G\). We determine the capture times exactly for trees and asymptotically for grids and cubes, and we give bounds on the capture time of planar graphs when the number of cops is 3 or \(\sqrt{n}\).

Event Topic

Discrete Applied Math Seminar