Cops and Robbers on Geometric Graphs

DOI10.1017/S0963548312000338zbMath1253.05104arXiv1108.2549WikidataQ57401436 ScholiaQ57401436MaRDI QIDQ3168443

Andrew Beveridge, Andrzej Dudek, Tobias Müller, Alan M. Frieze

Publication date: 31 October 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

random geometric graphs; connected geometric graph

Mathematics Subject Classification ID

60D05: Geometric probability and stochastic geometry

05C80: Random graphs (graph-theoretic aspects)

91A24: Positional games (pursuit and evasion, etc.)

05C57: Games on graphs (graph-theoretic aspects)

Related Items

On the contractibility of random Vietoris-Rips complexes, Chasing robbers on random geometric graphs-an alternative approach, Cops and robbers on intersection graphs, Visibility graphs, dismantlability, and the cops and robbers game, Chasing a drunk robber in many classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Almost all cop-win graphs contain a universal vertex
• The capture time of grids
• A framework for pursuit evasion games in
• On a pursuit game on Cayley graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• The longest edge of the random minimal spanning tree
• A game of cops and robbers played on products of graphs
• Vertex-to-vertex pursuit in a graph
• On the cover time and mixing time of random geometric graphs
• Variations on cops and robbers
• The cover time of random geometric graphs
• Chasing robbers on random graphs: Zigzag theorem
• Pursuit-Evasion in Models of Complex Networks
• A Bound for the Cops and Robbers Problem
• Solution of David Gale's lion and man problem