Name
Abstract | ||
|---|---|---|
The cop-number of a graph is the minimum number of cops needed to catch a robber on the graph, where the cops and the robber alternate moving from a vertex to a neighbouring vertex. It is conjectured by Meyniel that for a graph on n vertices O(n) cops suffice. The aim of this paper is to investigate the cop-number of a random graph. We prove that for sparse random graphs the cop-number has order of magnitude n^1^/^2^+^o^(^1^). The best known strategy for general graphs is the area-defending strategy, where each cop 'controls' one region by himself. We show that, for general graphs, this strategy cannot be too effective: there are graphs that need at least n^1^-^o^(^1^) cops for this strategy. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jctb.2012.10.002 | Journal of Combinatorial Theory Series B |
Keywords | Field | DocType |
general graph,area-defending strategy,cops suffice,known strategy,random graph,sparse random graph,magnitude n,n vertices O,neighbouring vertex,minimum number | Block graph,Discrete mathematics,Random regular graph,Combinatorics,Outerplanar graph,Tree-depth,Line graph,Cycle graph,Pathwidth,Symmetric graph,Mathematics | Journal |
Volume | Issue | ISSN |
103 | 2 | 0095-8956 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bela Bollobas | 1 | 66 | 12.05 |
| Gabor Kun | 2 | 20 | 1.09 |
| Imre Leader | 3 | 266 | 49.79 |