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

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