UVictoria Discrete Math Seminar: Amanda Porter

The game of Cops and Robbers is a two-player pursuit–evasion game played on a graph, in which a set of cops attempt to capture a single robber. The players occupy vertices of the graph and take turns moving along edges; capture occurs when a cop and the robber occupy the same vertex. In this talk, we explore classical results of Aigner and Fromme (1984) concerning the cop number of a graph—the minimum number of cops required to guarantee capture of the robber. In particular, we discuss two contrasting results: one that provides a class of graphs with arbitrarily large cop number, and another that identifies a class of graphs with a small cop number.