Meyniel's conjecture holds for random graphs

DOI10.1002/rsa.20587zbMath1332.05096arXiv1301.2841OpenAlexW2036458938WikidataQ123181686 ScholiaQ123181686MaRDI QIDQ2795750

Paweł Prałat, Nicholas C. Wormald

Publication date: 22 March 2016

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

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

zbMATH Keywords

random graphscops and robbersvertex-pursuit gamesexpansion properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

To catch a falling robber, 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, 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, Almost all \(k\)-cop-win graphs contain a dominating set of cardinality \(k\), Cops and Robbers on diameter two graphs, Meyniel's conjecture holds for random graphs, Chasing robbers on random geometric graphs-an alternative approach, Conjectures on Cops and Robbers

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Sandwiching random graphs: universality between random graph models
• Cops and robbers in a random 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
• A better bound for the cop number of general graphs