Chasing robbers on percolated random geometric graphs

Contributions to Discrete Mathematics

Anshui Li²  Tobias Muller²  Pawel Pralat¹ 

[1] Ryerson University;Utrecht University

关键词: Resolvable graph decomposition;    uniformly resolvable designs;    paths;   

DOI  :  

学科分类：社会科学、人文和艺术（综合）

来源: University of Calgary * Department of Mathematics and Statistics

【 摘 要 】

In this paper, we study the vertex pursuit game of \emph{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]^2$, and two vertices are adjacent with probability $p$ if the Euclidean distance between them is at most $r$. We present asymptotic results for the game of Cops and Robber played on $\G(n,r,p)$ for a wide range of $p=p(n)$ and $r=r(n)$.

【 授权许可】

Unknown