On the cop number of graphs of high girth
share
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 δ is at least 1g(δ - 1)^⌊g-1/4⌋. We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent 14g in this lower bound cannot be improved to (14+ε)g, we are also able to prove that it cannot be increased beyond 3/8g. 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.
READ FULL TEXT