Variations on cops and robbers

✍ Scribed by Alan Frieze; Michael Krivelevich; Po-Shen Loh

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 215 KB
• Volume: 69
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20591

✦ Synopsis

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 n^1 − 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(loglog__n__)^2^/log__n__). Our approach is based on expansion. © 2011 Wiley Periodicals, Inc. J Graph Theory.