Chasing robbers on random graphs: Zigzag theorem

DOI10.1002/rsa.20338zbMath1209.05226MaRDI 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 graphs; adjacency property; domination; cops and robbers; complex networks; vertex-pursuit games

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

91A43: Games involving graphs

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item