Abstract
In this paper, we study the vertex pursuit game of Cops and Robbers, in which cops try to capture a robber on the vertices of a 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(n; r; p), a percolated random geometric graph in which n vertices are chosen uniformly at random and independently from [0; 1]<sup>2</sup>. Two vertices are adjacent with probability p if the Euclidean distance between them is at most r. If the distance is bigger then r then they are never adjacent. We present asymptotic results for the game of Cops and Robbers played on G(n; r; p) for a wide range of p = p(n) and r = r(n)
Original language | English |
---|---|
Pages (from-to) | 134-144 |
Number of pages | 11 |
Journal | Contributions to Discrete Mathematics |
Volume | 10 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2015 |
Keywords
- Cops and robbers
- Random graphs