Chasing robbers on random geometric graphs-an alternative approach

DOI10.1016/J.DAM.2014.06.004zbMATH Open1300.05176arXiv1401.3313OpenAlexW2069386249MaRDI QIDQ741544FDOQ741544

Authors: Noga Alon, Paweł Prałat 

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We study the vertex pursuit game of emph{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 $G_d(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 $r^{3d-1}>c_{d}fraclognn$ 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 cite{bdfm}, using a different approach. Our method provides a tight $O(1/r^2)$ upper bound for the number of rounds needed to catch the robber.

Full work available at URL: https://arxiv.org/abs/1401.3313

Recommendations

• Cops and robbers on geometric graphs
• Chasing robbers on percolated random geometric graphs
• Cops and robbers in a random graph
• When does a random graph have constant cop number?
• Chasing robbers on random graphs: zigzag theorem

zbMATH Keywords

cops and robbersrandom graphsvertex-pursuit games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Random Geometric Graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• Cops and robbers in a random graph
• Meyniel's conjecture holds for random graphs
• Variations on cops and robbers
• On Meyniel's conjecture of the cop number
• Chasing robbers on random graphs: zigzag theorem
• Pursuit-evasion in models of complex networks
• The game of cops and robbers on graphs
• A bound for the cops and robbers problem
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• A framework for pursuit evasion games in
• Title not available (Why is that?)
• When does a random graph have constant cop number?
• Searching and sweeping graphs: a brief survey
• Title not available (Why is that?)
• Solution of David Gale's lion and man problem
• A better bound for the cop number of general graphs
• On a generalization of Meyniel's conjecture on the Cops and Robbers game
• Cops and robbers on geometric graphs

Cited In (4)

• On the contractibility of random Vietoris-Rips complexes
• Chasing robbers on random graphs: zigzag theorem
• Cops and robbers on geometric graphs
• When does a random graph have constant cop number?

This page was built for publication: Chasing robbers on random geometric graphs-an alternative approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741544)