On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game

Abstract

We consider a variant of the Cops and Robbers game where the robber can move $s$ edges at a time, and show that in this variant, the cop number of a connected graph on $n$ vertices can be as large as $\Omega(n^\frac{s}{s+1})$. This improves the $\Omega(n^{\frac{s-3}{s-2}})$ lower bound of Frieze et al., and extends the result of the second author, which establishes the above bound for $s=2,4$.