Cops and robbers in random graphs
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
15 pages. J. Comb. Theory B, submitted
15 pages. J. Comb. Theory B, submitted