Chasing robbers on random geometric graphs-An alternative approach

We study the vertex pursuit game of Cops and Robbers, in which cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. We focus on Gd(n,r), a random geometric graph in which n vertices are chosen uniformly at random and independently from [0,1]d, and two vertices are adjacent if the Euclidean distance between them is at most r. The main result is that if r3d−1>cdlognn then the cop number is 1 with probability that tends to 1 as n tends to infinity. The case d=2 was proved earlier and independently in Beveridge et al. (2012), using a different approach. Our method provides a tight O(1/r2) upper bound for the number of rounds needed to catch the robber.