Lower Bounds for the Cop Number when the Robber is Fast
Abbas Mehrabian · Combinatorics Probability Computing · 2011
We consider a variant of the Cops and Robbers game where the robber can move t edges at a time, and show that in this variant, the cop number of a d -regular graph with girth larger than 2 t +2 is Ω( d t ). By the known upper bounds on the order of cages, this implies that the cop number of a connected n -vertex graph can be as large as Ω( n 2/3 ) if t ≥ 2, and Ω( n 4/5 ) if t ≥ 4. This improves the Ω( $n^{\frac{t-3}{t-2}}$ ) lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers, J. Graph Theory , to appear) when 2 ≤ t ≤ 6. We also conjecture a general upper bound O ( n t / t +1 ) for the cop number in this variant, generalizing Meyniel's conjecture.