TY - JOUR

T1 - Chasing robbers on random geometric graphs - An alternative approach

AU - Alon, Noga

AU - Prałat, Paweł

N1 - Funding Information:
The first author acknowledges support by an ERC Advanced grant, by a USA-Israeli BSF grant ( 0603804531 ), and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. The second author acknowledges support from NSERC ( 418059-2012 ) and Ryerson University .
Publisher Copyright:
© 2014 Elsevier Ltd. All rights reserved.

PY - 2014/12/11

Y1 - 2014/12/11

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

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

KW - Cops and Robbers

KW - Random graphs

KW - Vertex-pursuit games

UR - http://www.scopus.com/inward/record.url?scp=84907712296&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84907712296&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2014.06.004

DO - 10.1016/j.dam.2014.06.004

M3 - Article

AN - SCOPUS:84907712296

SN - 0166-218X

VL - 178

SP - 149

EP - 152

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -