Chasing a Fast Robber on Planar Graphs and Random Graphs

DOI10.1002/jgt.21791zbMath1305.05142OpenAlexW1913504200MaRDI QIDQ2940989

Noga Alon, Abbas Mehrabian

Publication date: 21 January 2015

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21791

zbMATH Keywords

random graphsplanar graphstreewidthdomination numbercops and robber gamefast robber

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (10)

Network decontamination with a single agent ⋮ A probabilistic version of the game of zombies and survivors on graphs ⋮ Catching an infinitely fast robber on a grid ⋮ An Introduction to Lazy Cops and Robbers on Graphs ⋮ Cops and Robber game with a fast robber on expander graphs and random graphs ⋮ Lazy Cops and Robbers on Hypercubes ⋮ The fast robber on interval and chordal graphs ⋮ Escaping an Infinitude of Lions ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Containment game played on random graphs: another zig-zag theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Cops and robbers from a distance
• On a generalization of Meyniel's conjecture on the Cops and Robbers game
• A game of cops and robbers
• The treewidth and pathwidth of hypercubes
• Linearity of grid minors in treewidth with applications through bidimensionality
• A witness version of the cops and robber game
• Cops and robbers in graphs with large girth and Cayley graphs
• Graph searching and a min-max theorem for tree-width
• Vertex-to-vertex pursuit in a graph
• Cops and Robber game with a fast robber on expander graphs and random graphs
• Cops and robbers in a random graph
• Pursuing a fast robber on a 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
• A Bound for the Cops and Robbers Problem
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• A Separator Theorem for Nonplanar Graphs
• An Optimal Synchronizer for the Hypercube
• Bidimensional Parameters and Local Treewidth
• Randomized Pursuit-Evasion with Local Visibility

This page was built for publication: Chasing a Fast Robber on Planar Graphs and Random Graphs