Combinatorics, Probability and Computing

Paper

Lower Bounds for the Cop Number when the Robber is Fast

ABBAS MEHRABIANa1

a1 Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1 (e-mail: amehrabian@uwaterloo.ca)

Abstract

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 Ω($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(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)