file.pdf (225.35 kB)

Variations on Cops and Robbers

Download (225.35 kB)
journal contribution
posted on 01.11.2010, 00:00 by Alan Frieze, Michael Krivelevich, Po-Shen Loh

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

History

Publisher Statement

This is the accepted version of the article which has been published in final form at http://dx.doi.org/10.1002/jgt.20591

Date

01/11/2010

Exports

Exports