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 graphsconnected geometric graph

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Random graphs (graph-theoretic aspects) (05C80) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Cops and robbers on intersection graphs, On the contractibility of random Vietoris-Rips complexes, Visibility graphs, dismantlability, and the cops and robbers game, Cops and robber on butterflies, grids, and AT-free graphs, Chasing robbers on random geometric graphs-an alternative approach, 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