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 attempts to capture a single robber. In the original version, players occupy vertices and take turns moving along edges. We describe a variant, introduced by Dudek, Gordinowicz, and Prałat (2014), where players occupy edges and move through incident vertices; capture occurs when a cop and the robber occupy the same edge. We present two contrasting results on the edge cop number of a graph—the minimum number of cops needed to guarantee capture of the robber. One result provides a class of graphs with small edge cop number, while the other identifies a class with an arbitrarily large edge cop number.