2010/04/14 by Frieze, Alan, Krivelevich, Michael, Loh, Po-Shen · 1 citation
#05C20 #05C35 #05C57 #05D40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1004.2482
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 N / α(1-o(1))√(logα N), where α = 1 + 1/R, thus generalizing the best known upper bound for the classical case R = 1 due to Lu and Peng. 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, 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 at most O(N(log log N)2/log N). Our approach is based on expansion.