Surrounding cops and robber: a vertex-pursuit game

Abstract:

The vertex-pursuit game of cops and robbers, introduced by Nowakowski and Winkler (1983), is played on a graph where a team of cops aim to occupy the same vertex as the robber. The cop number of a graph is the least number of cops required to guarantee capture, and this is conjectured to be $O(\sqrt{n})$ for a graph on n vertices. In search of an upper bound on the cop number of a graph, we introduce a variant of the original game whereby the cops aim to occupy each of the robber's neighbouring vertices. The surrounding cop number $\sigma(G)$ of a graph $G$ is the least number of cops required to surround a robber in $G.$

In this talk I will present a number of results and open problems regarding the surrounding cop number. Results include general bounds as well as exact values for several classes of graphs. Particular classes of interest include product graphs, graphs arising from combinatorial designs, and generalised Petersen graphs.

Joint work with Andrea Burgess, Nancy Clarke, Peter Danziger, Stephen Finbow, Caleb Jones and David Pike.

This is a seminar of the Combinatorial Mathematics Society of Australasia.

To attend email cmsa-webinar@monash.edu with the subject 'subscribe' to receive zoom details. [You only need to subscribe once, not for future talks.]