Premium
Variations on cops and robbers
Author(s) -
Frieze Alan,
Krivelevich Michael,
Loh PoShen
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20591
Subject(s) - combinatorics , digraph , mathematics , upper and lower bounds , vertex (graph theory) , graph , discrete mathematics , mathematical analysis
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.