Cops and Robbers on Geometric Graphs

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 x ₁, . . ., x_n ∈ ℝ², and r ∈ ℝ⁺, the vertex set of the geometric graph G(x ¹, . . ., x_n; r) is the graph on these npoints, with x_i, x_j adjacent when ∥x_i − x_j ∥ ≤ r. We prove that c(G) ≤ 9 for any connected geometric graph G in ℝ² 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 nvertices chosen uniformly and independently from [0,1]². For G ∈ (n,r), we show that with high probability (w.h.p.), ifr ≥ K ₁ (log n/n)^1/4 then c(G) ≤ 2, and if r ≥ K ₂(log n/n)^1/5 then c(G) = 1, where K ₁, K ₂ > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r ≤ K ₃ log n/ then c(G) > 1 w.h.p., where K ₃ > 0 is an absolute constant.