Cops and Robbers on diameter two graphs

Zsolt A. Wagner

Published 2013-12-29, updated 2014-09-28Version 3

In this short paper we study the game of Cops and Robbers, played on the vertices of some fixed graph $G$ of order $n$. The minimum number of cops required to capture a robber is called the cop number of $G$. We show that the cop number of graphs of diameter 2 is at most $\sqrt{2n}$, improving a recent result of Lu and Peng by a constant factor. We conjecture that this bound is still not optimal, and obtain some partial results towards the optimal bound.