On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game - Alon, Noga; Mehrabian, Abbas (The Electronic Journal of Combinatorics, 2011)
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 $Ω(n^\frac{s}{s+1})$. This improves the $Ω(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$.