Cops and robbers in random graphs

@misc{citeulike:2831644, abstract = {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.}, author = {Bollobas, Bela and Kun, Gabor and Leader, Imre }, citeulike-article-id = {2831644}, eprint = {0805.2709}, keywords = {cops}, month = {May}, posted-at = {2008-05-25 22:01:27}, priority = {2}, title = {Cops and robbers in random graphs}, url = {http://arxiv.org/abs/0805.2709}, year = {2008} }

TY - ELEC ID - citeulike:2831644 L3 - citeulike-article-id:2831644 TI - Cops and robbers in random graphs N2 - 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. KW - cops AU - Bollobas, Bela AU - Kun, Gabor AU - Leader, Imre PY - 2008/May/18/ UR - http://arxiv.org/abs/0805.2709 ER -