Cops and Robbers on Geometric GraphsAndrew Beveridge∗, Andrzej Dudek†, Alan Frieze‡, Tobias M¨uller§July 4, 2012AbstractCops and robbers is a turn-based pursuit game played on a graph G. One robber ispursued by a set of cops. In each round, these agents move between vertices along theedges of the graph. The cop number c(G) denotes the minimum number of cops required tocatch the robber in finite time. We study the cop number of geometric graphs. For pointsx1, . . . , xn∈ R2, and r ∈ R+, the vertex set of the geometric graph G(x1, . . . , xn; r) is thegraph on these n points, with xi, xjadjacent when kxi− xjk ≤ r. We prove that c(G) ≤ 9for any connected geometric graph G in R2and we give an example of a connected geometricgraph with c(G) = 3. We improve on our upper bound for random geometric graphs thatare sufficiently dense. Let G(n, r) denote the probability space of geometric graphs with nvertices chosen uniformly and independently from [0, 1]2. For G ∈ G(n, r), we show thatwith high probability (whp), if r ≥ K1(log n/n)14, then c(G) ≤ 2, and if r ≥ K2(log n/n)15,then c(G) = 1 where K1, K2> 0 are absolute constants. Finally, we provide a lower boundnear the connectivity regime of G(n, r): if r ≤ K3log n/√n then c(G) > 1 whp, whereK3> 0 is an absolute constant.1 IntroductionThe game of cops and robbers is a full information game played on a graph G. The game wasintroduced independently by Nowakowski and Winkler [26] and Quilliot [31]. During play, one∗Department of Mathematics, Statistics and Computer Science, Macalester College, Saint Paul, MN:[email protected]†Department of Mathematics, Western Michigan University, Kalamazoo, MI: [email protected]‡Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA:[email protected]. Supported in part by NSF Grant CCF1013110§Centrum voor Wiskunde en Informatica, Amsterdam, the Netherlands: [email protected]. Supported in partby a VENI grant from Netherlands Organization for Scientific Research (NWO)1robber R is pursued by a set of cops C1, . . . , C`. Initially, the cops choose their locations on thevertex set. Next, the robber chooses his location. The cops and the robber are aware of thelocation of all agents during play, and the cops can coordinate their motion. On the cop turn,each cop moves to an adjacent vertex, or remains stationary. This is followed by the robberturn, and he moves similarly. The game continues with the players alternating turns. The copswin if they can catch the robber in finite time, meaning that some cop is colocated with therobber. The robber wins if he can evade capture indefinitely.The original formulation [26, 31] concerned a single cop chasing the robber. These paperscharacterized the structure of cop-win graphs for which a single cop has a winning strategy.For v ∈ V (G), the neighborhood of v is N(v) = {u ∈ V (G) | (u, v) ∈ E(G)} and the closedneighborhood of v is N(v) = {v} ∪ N(v). When N(u) ⊆ N (v), we say that u is a pitfall. Agraph is dismantlable if we can reduce G to a single vertex by successively removing pitfalls.Theorem 1.1 ([26, 31]) G is dismantlable if and only if c(G) = 1.Aigner and Fromme [1] introduced the multiple cop variant described above. For a fixedgraph G, they defined the cop number c(G) as the minimum number of cops for which there isa winning cop strategy on G. Among their results, they proved the following.Theorem 1.2 ([1]) If G is a connected planar graph, then c(G) ≤ 3.Various authors have studied the cop number of families of graphs [13, 12, 24, 25]. Recently,significant attention has been directed towards Meyniel’s conjecture (found in [12]) that c(G) =O(√n) for any n vertex graph. The best current bound is c(G) ≤ n2−(1+o(1))√log n, obtainedindependently in [22, 32, 14]. The history of Meyniel’s conjecture is surveyed in [5]. For furtherresults on vertex pursuit games on graphs, see the surveys [3, 17] and the monograph [9].Herein, we study the game of cops and robbers on geometric graphs in R2. Given pointsx1, . . . , xn∈ R2and r ∈ R+, the geometric graph G = G(x1, . . . , xn; r) has vertices V (G) ={1, . . . , n} and ij ∈ E(G) if and only if kxi− xjk ≤ r. Geometric graphs are widely used tomodel ad-hoc wireless networks [16, 34]. For convenience, we will consider V (G) = {x1, . . . xn},referring to “point xi” or “vertex xi” when this distinction is required. Our first result gives aconstant upper bound on the cop number of 2-dimensional geometric graphs.Theorem 1.3 If G is a connected geometric graph in R2, then c(G) ≤ 9.The proof of this theorem is an adaptation of the proof of Theorem 1.2. This adaptation requiresthree cops on a geometric graph to play the role of a single cop on a planar graph. We also give2an example of a geometric graph requiring 3 cops.Recent years have witnessed significant interest in the study of random graph models, moti-vated by the need to understand complex real world networks. In this setting, the game of copsand robbers is a simplified model for network security. There are many recent results on copsand robbers on random graph models, including the Erd˝os-Renyi model and random power lawgraphs [7, 23, 29, 10, 8, 30]. We add to this list of stochastic models by considering cops androbbers on random geometric graphs. A random geometric graph G on [0, 1]2contains of npoints drawn uniformly at random. Two points x, y ∈ V (G) are adjacent when the distancebetween them is within the connectivity radius, i.e. kx − yk ≤ r. We denote the probabilityspace of random geometric graphs by G(n, r). Typically, we view the radius as a function r(n),and then study the asymptotic properties of G(n, r) as n increases. We say that event A oc-curs with high probability, or whp, when P[A] = 1 − o(1) as n tends to infinity, or equivalently,limn→∞P[A] = 1. For example, G ∈ G(n, r) is connected whp if r =qlog n+ω(n)π n. (Here and inthe remainder of this paper, ω(n) denotes an arbitrarily slowly growing function.) For this andfurther results on G(n, r), see the monograph [28].We improve on the bound of Theorem 1.3 when our random geometric graph is sufficientlydense. Essentially, we determine thresholds for which we can successfully adapt known pursuitevasion strategies to the geometric graph setting. Typical analysis of G(n, r) focusses on thehomogeneous aspects of the resulting graph, resulting from tight concentration around