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 Ω(ns/s+1) This improves the Ω(ns-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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics