Chasing robbers on percolated random geometric graphs

Anshui Li, Tobias Müller, Paweł Prałat

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)134-144
Number of pages11
JournalContributions to Discrete Mathematics
Volume10
Issue number1
DOIs
Publication statusPublished - 2015

Keywords

  • Cops and robbers
  • Random graphs

Fingerprint

Dive into the research topics of 'Chasing robbers on percolated random geometric graphs'. Together they form a unique fingerprint.

Cite this