Variations on Cops and Robbers

<p>We consider several variants of the classical Cops and Robbers game. We treat the version where the robber can move <em>R</em>≥1 edges at a time, establishing a general upper bound of , where α = 1 + 1/<em>R</em>, thus generalizing the best known upper bound for the classical case <em>R</em> = 1 due to Lu and Peng, and Scott and Sudakov. We also show that in this case, the cop number of an <em>n</em>-vertex graph can be as large as <em>n</em>^{1 − 1/(<em>R</em> − 2)} for finite <em>R</em>≥5, but linear in <em>n</em> if <em>R</em> is infinite. For <em>R</em> = 1, we study the directed graph version of the problem, and show that the cop number of any strongly connected digraph on <em>n</em> vertices is <em>O</em>(<em>n</em>(loglog<em>n</em>)²/log<em>n</em>). Our approach is based on expansion.</p>