The capture time of a graph

DOI10.1016/j.disc.2008.04.004zbMath1177.91056OpenAlexW2035417355MaRDI QIDQ1045043

Jan Kratochvíl, Anthony Bonato, Geňa Hahn, Petr A. Golovach

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.004

zbMATH Keywords

graphchordal graphNP-completecop numberinfinite random graphsearch numbercapture timebounded-time cop number

Mathematics Subject Classification ID

Games involving graphs (91A43) Structural characterization of families of graphs (05C75)

Related Items (35)

Cop vs. gambler ⋮ The capture time of a planar graph ⋮ Capture times in the bridge-burning cops and robbers game ⋮ Unnamed Item ⋮ Game with Slow Pursuers on the Edge Graphs of Regular Simplexes ⋮ Unnamed Item ⋮ Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond ⋮ Pursuit evasion on infinite graphs ⋮ Differential Game with Slow Pursuers on the Edge Graph of a Simplex ⋮ TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS ⋮ Constructible graphs and pursuit ⋮ The damage throttling number of a graph ⋮ Containment: a variation of cops and robber ⋮ The game of overprescribed Cops and Robbers played on graphs ⋮ The capture time of grids ⋮ Capturing the drunk robber on a graph ⋮ On the Capture Time of Cops and Robbers Game on a Planar Graph ⋮ Visibility graphs, dismantlability, and the cops and robbers game ⋮ A tight lower bound for the capture time of the cops and robbers game ⋮ Fast edge searching and fast searching on graphs ⋮ The capture time of the hypercube ⋮ The impact of loops on the game of cops and robbers on graphs ⋮ Zombie number of the Cartesian product of graphs ⋮ Cops and robbers ordinals of cop-win trees ⋮ Cop-win graphs with maximum capture-time ⋮ Throttling for the game of cops and robbers on graphs ⋮ Bounds on the length of a game of cops and robbers ⋮ The game of cops and eternal robbers ⋮ Capture-time extremal cop-win graphs ⋮ A pursuit-evasion differential game with slow pursuers on the edge graph of a simplex. I ⋮ Product throttling ⋮ Linguistic geometry approach for solving the cops and robber problem in grid environments ⋮ Conjectures on Cops and Robbers ⋮ The optimal capture time of the one-cop-moves game ⋮ The localization capture time of a graph

Cites Work

• The complexity of pursuit on a graph
• An annotated bibliography on guaranteed graph searching
• On the cop number of a graph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Vertex-to-vertex pursuit in a graph
• On cop-win graphs
• A note on \(k\)-cop, \(l\)-robber games on graphs
• The random graph
• Asymmetric graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The capture time of a graph