Contributions to Discrete Mathematics | |
Chasing robbers on percolated random geometric graphs | |
Anshui Li2  Tobias Muller2  Pawel Pralat1  | |
[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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201911300701866ZK.pdf | 330KB | download |