On a generalization of Meyniel's conjecture on the Cops and Robbers game (Q625381): Difference between revisions

Summary: 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. [\textit{A. Frieze}, \textit{M. Krivelevich}, and \textit{P. Loh}, ``Variations on cops and robbers,'' \url{arXiv:1004.2482}], and extends the result of the second author [\textit{A. Mehrabian}, ``Lower bounds for cop number when robber is fast,'' \url{arXiv:1007.1734}], which establishes the above bound for \(s = 2, 4\).