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 and take turns moving along edges; capture occurs when a cop and the robber occupy the same vertex. In this talk, we examine a result of Maamoun and Meyniel (1987) determining the cop number of the Cartesian product of trees— the minimum number of cops required to guarantee capture of the robber. After reviewing the rules of the game and the structure of the Cartesian product, we outline the main ideas behind both the lower and upper bound for this cop number.