Variations on Cops and Robbers

Details Variations on Cops and Robbers Variations on Cops and Robbers

2010-04-14

arxiv.org/abs/1004.2482v1

Mathematics

Combinatorics

18 pages

Scientific paper

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 / \alpha ^{(1-o(1))\sqrt{log_\alpha N}}, where \alpha = 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 N^{1 - 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.

Affiliated with

Also associated with

No associations

Rating

Variations on Cops and Robbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Variations on Cops and Robbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variations on Cops and Robbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-528412