Cops and Robbers on Geometric Graphs

<p>Cops and robbers is a turn-based pursuit game played on a graph <em>G</em>. 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 <em>c</em>(<em>G</em>) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points <em>x</em> ₁, . . ., <em>x_n </em>∈ ℝ², and <em>r</em> ∈ ℝ⁺, the vertex set of the geometric graph <em>G(x</em> ¹, . . ., <em>x_n; r</em>) is the graph on these <em>n</em>points, with <em>x_i, x_j </em>adjacent when ∥<em>x_i </em>− <em>x_j </em>∥ ≤ <em>r</em>. We prove that <em>c</em>(<em>G</em>) ≤ 9 for any connected geometric graph <em>G</em> in ℝ² and we give an example of a connected geometric graph with <em>c</em>(<em>G</em>) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (<em>n,r</em>) denote the probability space of geometric graphs with <em>n</em>vertices chosen uniformly and independently from [0,1]². For <em>G</em> ∈ (<em>n,r</em>), we show that with high probability (w.h.p.), if<em>r</em> ≥ <em>K</em> ₁ (log <em>n/n</em>)^1/4 then <em>c</em>(<em>G</em>) ≤ 2, and if <em>r</em> ≥ <em>K</em> ₂(log <em>n/n</em>)^1/5 then <em>c</em>(<em>G</em>) = 1, where <em>K</em> ₁, <em>K</em> ₂ > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (<em>n,r</em>): if <em>r</em> ≤ <em>K</em> ₃ log <em>n</em>/ then <em>c</em>(<em>G</em>) > 1 w.h.p., where <em>K</em> ₃ > 0 is an absolute constant.</p>