## Abstract

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 G_{d}(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 r^{3d-1}>c_{d}lognn 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/r^{2}) upper bound for the number of rounds needed to catch the robber.

Original language | English (US) |
---|---|

Pages (from-to) | 149-152 |

Number of pages | 4 |

Journal | Discrete Applied Mathematics |

Volume | 178 |

DOIs | |

State | Published - Dec 11 2014 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Keywords

- Cops and Robbers
- Random graphs
- Vertex-pursuit games