Cops and robbers in random graphs
| dc.creator | Bollobas, Bela | |
| dc.creator | Kun, Gabor | |
| dc.creator | Leader, Imre | |
| dc.date | 2008-05-18 | |
| dc.date.accessioned | 2026-07-07T09:39:38Z | |
| dc.date.available | 2026-07-07T09:39:38Z | |
| dc.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. | |
| dc.description | 15 pages. J. Comb. Theory B, submitted | |
| dc.identifier | https://arxiv.org/abs/0805.2709 | |
| dc.identifier | http://arxiv.org/abs/0805.2709 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/161243 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80 | |
| dc.title | Cops and robbers in random graphs | |
| dc.type | text |