On the cop number of graphs of high girth

Abstract

We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in particular, that the cop number of any graph with girth $g$ and minimum degree $\delta$ is at least $\frac{1}{g}(\delta -1{)}^{\lfloor \frac{g-1}{4}\rfloor }$. We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent $\frac{1}{4}g$ in this lower bound cannot be improved to $(\frac{1}{4}+\epsilon )g$, we are also able to prove that it cannot be increased beyond $\frac{3}{8}g$. This is established by considering a certain family of Ramanujan graphs. In our proof of this bound, we also show that the "weak" Meyniel's conjecture holds for expander graph families of bounded degree.

18 pages, 1 figure