A Bound for the Cops and Robbers Problem

DOI10.1137/100812963zbMath1237.05132arXiv1004.2010OpenAlexW2054375402MaRDI QIDQ3225131

Benjamin Sudakov, Alexander D. Scott

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pursuit-evasion gamesgames on graphscop numbergraph searching

Mathematics Subject Classification ID

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

Related Items (28)

To catch a falling robber ⋮ Cops and Robbers on Geometric Graphs ⋮ Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond ⋮ The game of cops and robbers on directed graphs with forbidden subgraphs ⋮ Catching a fast robber on the grid ⋮ Cops and robbers from a distance ⋮ Chasing a Fast Robber on Planar Graphs and Random Graphs ⋮ Cops and Robber game with a fast robber on expander graphs and random graphs ⋮ Cops and Robbers on Dynamic Graphs: Offline and Online Case ⋮ The node cop‐win reliability of unicyclic and bicyclic graphs ⋮ On the cop number of graphs of high girth ⋮ Cops and robber on subclasses of \(P_5\)-free graphs ⋮ The one-cop-moves game on graphs with some special structures ⋮ The fast robber on interval and chordal graphs ⋮ Cops and Robbers on diameter two graphs ⋮ Cops and Robbers on Graphs of Bounded Diameter ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ Study of a combinatorial game in graphs through linear programming ⋮ Bounding the Cop Number of a Graph by Its Genus ⋮ A proof of the Meyniel conjecture for abelian Cayley graphs ⋮ Meyniel's conjecture holds for random graphs ⋮ 4-cop-win graphs have at least 19 vertices ⋮ Chasing robbers on random geometric graphs-an alternative approach ⋮ Unnamed Item ⋮ Conjectures on Cops and Robbers ⋮ The optimal capture time of the one-cop-moves game ⋮ Meyniel extremal families of abelian Cayley graphs

This page was built for publication: A Bound for the Cops and Robbers Problem