Chasing robbers on random graphs: Zigzag theorem

DOI10.1002/rsa.20338zbMath1209.05226OpenAlexW4256158764MaRDI QIDQ3061185

Paweł Prałat, Tomasz Łuczak

Publication date: 14 December 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20338

zbMATH Keywords

random graphsadjacency propertydominationcops and robberscomplex networksvertex-pursuit games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43)

Related Items (25)

To catch a falling robber ⋮ Variations on cops and robbers ⋮ Cops and Robbers on Geometric Graphs ⋮ Subdivisions in the robber locating game ⋮ On Meyniel's conjecture of the cop number ⋮ Cops and robbers from a distance ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ The game of overprescribed Cops and Robbers played on graphs ⋮ Cops and invisible robbers: the cost of drunkenness ⋮ Some remarks on cops and drunk robbers ⋮ Cops and Robber game with a fast robber on expander graphs and random graphs ⋮ Cops and Robbers on Dynamic Graphs: Offline and Online Case ⋮ Counting extensions revisited ⋮ Meyniel's conjecture on graphs of bounded degree ⋮ On the cop number of graphs of high girth ⋮ Almost all cop-win graphs contain a universal vertex ⋮ Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs ⋮ Almost all \(k\)-cop-win graphs contain a dominating set of cardinality \(k\) ⋮ Cops and Robbers on diameter two graphs ⋮ The robber locating game ⋮ Revolutionaries and Spies on Random Graphs ⋮ Meyniel's conjecture holds for random graphs ⋮ Chasing robbers on random geometric graphs-an alternative approach ⋮ Containment game played on random graphs: another zig-zag theorem ⋮ Meyniel extremal families of abelian Cayley graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• On the Choice Number of Random Hypergraphs
• Pursuit-Evasion in Models of Complex Networks
• A better bound for the cop number of general graphs

This page was built for publication: Chasing robbers on random graphs: Zigzag theorem