Chasing robbers on random geometric graphs---an alternative approach

Abstract

We study the vertex pursuit game of \emph{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\frac{\log n}{n}$ 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 \cite{bdfm}, 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.

6 pages

References in corpus (2)

• Meyniel's conjecture holds for random d-regular graphs
• Meyniel's conjecture holds for random graphs