Chasing robbers on random geometric graphs - An alternative approach

Noga Alon, Paweł Prałat

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We study the vertex pursuit game of Cops and Robbers, in which cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. We focus on Gd(n,r), a random geometric graph in which n vertices are chosen uniformly at random and independently from [0,1]d, and two vertices are adjacent if the Euclidean distance between them is at most r. The main result is that if r3d-1>cdlognn then the cop number is 1 with probability that tends to 1 as n tends to infinity. The case d=2 was proved earlier and independently in Beveridge et al. (2012), using a different approach. Our method provides a tight O(1/r2) upper bound for the number of rounds needed to catch the robber.

Original languageEnglish (US)
Pages (from-to)149-152
Number of pages4
JournalDiscrete Applied Mathematics
Volume178
DOIs
StatePublished - Dec 11 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Cops and Robbers
  • Random graphs
  • Vertex-pursuit games

Fingerprint

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

Cite this