Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Anthony Bonato

Ryerson University

Problems and conjectures on Cops and Robbers

Abstract:

\emph{Cops and Robbers} is a vertex pursuit game played on graphs which has gained considerable recent attention. An intruder (or \emph{robber})\ is loose on a network and some number of agents (or \emph{cops}) are trying to capture him. The players are restricted to vertices, and move to neighboring vertices along edges at alternate ticks of the clock. The minimum number of cops needed to capture the robber is called the \emph{cop number}. The most famous open problem on the cop number is \emph{Meyniel's conjecture}, which claims that for a connected graph $G$ of order $n,$ $ c(G)=O(\sqrt{n}).$ We consider this and other conjectures and problems related to graphs with large cop number, algorithms for computing the cop number, and the cop number of planar graphs.

Host: Jacques Verstraete

August 30, 2011

4:00 PM

AP&M 7321

****************************