Variations on cops and robbers |
| |
Authors: | Alan Frieze Michael Krivelevich Po‐Shen Loh |
| |
Affiliation: | 1. Department of mathematical sciences carnegie mellon university pittsburgh, , pennsylvania, 15213;2. School of mathematical sciences raymond and beverly sackler faculty of exact sciences, tel aviv university tel aviv, , 69978 israel |
| |
Abstract: | 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. © 2011 Wiley Periodicals, Inc. J Graph Theory. |
| |
Keywords: | Cop number Meyniel's conjecture Games on graphs |
|
|