Chasing robbers on random geometric graphs-an alternative approach

DOI10.1016/J.DAM.2014.06.004MaRDI QIDQ741544zbMATH OpenOpenAlexFDO

Authors Noga Alon, Paweł Prałat

Publication date 12 September 2014

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

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

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)

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.

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

Cites work

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

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)