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 $\tfrac{ 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 $\tfrac{ 1}{ 4}g$ in this lower bound cannot be improved to $(\tfrac{ 1}{ 4}+\varepsilon)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.
Categories: math.CO cs.DM