a1 Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1 (e-mail: [email protected])
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 2t+2 is Ω(dt). 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 Ω(n2/3) if t ≥ 2, and Ω(n4/5) if t ≥ 4. This improves the Ω() 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(nt/t+1) for the cop number in this variant, generalizing Meyniel's conjecture.
(Received July 10 2010)
(Revised January 28 2011)
(Online publication April 19 2011)