Chasing robbers on percolated random geometric graphs

Authors

  • Anshui Li Utrecht University
  • Tobias Muller Utrecht University
  • Pawel Pralat Ryerson University

DOI:

https://doi.org/10.11575/cdm.v10i1.62293

Abstract

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).

Author Biography

Pawel Pralat, Ryerson University

Department of Mathematics

Associate Professor and Associate Chair for Research

Downloads

Published

2015-07-31

Issue

Section

Articles