Cops and Robbers on Geometric Graphs

Details Cops and Robbers on Geometric Graphs Cops and Robbers on Geometric Graphs

2011-08-12

arxiv.org/abs/1108.2549v4

Mathematics

Combinatorics

22 pages, 8 figures

Scientific paper

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_1, ..., x_n \in \R^2$, and $r \in \R^+$, the vertex set of the geometric graph $G(x_1, ..., x_n; r)$ is the graph on these $n$ points, with $x_i, x_j$ adjacent when $ \norm{x_i -x_j} \leq r$. We prove that $c(G) \leq 9$ for any connected geometric graph $G$ in $R^2$ 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 $G(n,r)$ denote the probability space of geometric graphs with $n$ vertices chosen uniformly and independently from $[0,1]^2$. For $G \in G(n,r)$, we show that with high probability (whp), if $r \geq K_1 (\log n/n)^{1/4}$, then $c(G) \leq 2$, and if $r \geq K_2(\log n/n)^{1/5}$, then $c(G) = 1$ where $K_1, K_2 > 0$ are absolute constants. Finally, we provide a lower bound near the connectivity regime of $G(n,r)$: if $r \leq K_3 \log n / \sqrt{n} $ then $c(G) > 1$ whp, where $K_3 > 0$ is an absolute constant.

Affiliated with

Also associated with

No associations

Rating

Cops and Robbers on Geometric Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cops and Robbers on Geometric Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cops and Robbers on Geometric Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-15821