Cops and robbers in random graphs

Details Cops and robbers in random graphs Cops and robbers in random graphs

2008-05-18

arxiv.org/abs/0805.2709v1

Mathematics

Combinatorics

15 pages. J. Comb. Theory B, submitted

Scientific paper

We consider the pursuit and evasion game on finite, connected, undirected graphs known as cops and robbers. Meyniel conjectured that for every graph on n vertices a rootish number of cops can win the game. We prove that this holds up to a log(n) factor for random graphs G(n,p) if p is not very small, and this is close to be tight unless the graph is very dense. We analyze the area-defending strategy (used by Aigner in case of planar graphs) and show examples where it can not be too efficient.

Affiliated with

Also associated with

No associations

Rating

Cops and robbers in random graphs 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 Cops and robbers in random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cops and robbers in random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-65936