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^ss+1). This improves the Ω(n^s-3s-2 ) lower bound of Frieze et al., and extends the result of the second author, which establishes the above bound for s=2,4.