Name
Abstract | ||
|---|---|---|
Cops and robbers is a turn-based pursuit game played on a graph G. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number c(G) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points x1,.ï戮 .ï戮 ., xn ∈ â聞聺2, and r ∈ â聞聺+, the vertex set of the geometric graph G(x1,.ï戮 .ï戮 ., xn; r) is the graph on these n points, with xi, xj adjacent when â聢楼xi-xjâ聢楼 â聣陇 r. We prove that c(G) â聣陇 9 for any connected geometric graph G in â聞聺2 and we give an example of a connected geometric graph with c(G) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (n,r) denote the probability space of geometric graphs with n vertices chosen uniformly and independently from [0,1]2. For G ∈ (n,r), we show that with high probability (w.h.p.), if r â聣楼 K1 (log n/n)1/4 then c(G) â聣陇 2, and if r â聣楼 K2(log n/n)1/5 then c(G) = 1, where K1, K2 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r â聣陇 K3 log n/ then c(G) 1 w.h.p., where K3 0 is an absolute constant. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/S0963548312000338 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random geometric graph,n vertex,connected geometric graph,n point,geometric graph,minimum number,k3 log n,log n,graph g.,cop number,upper bound,lower bound | Discrete mathematics,Geometric graph theory,Random regular graph,Combinatorics,Line graph,Graph power,Bound graph,Cycle graph,Symmetric graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
21 | 6 | 0963-5483 |
Citations | PageRank | References |
4 | 0.47 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Alan M. Frieze | 3 | 4837 | 787.00 |
| Tobias Müller | 4 | 33 | 5.37 |