Abstract: We consider the game of Cops and Robber played on the Cartesian product of two trees. Assuming the players play perfectly, it is shown that if there are two cops in the game, then the length of the game (known as the 2-capture time of the graph) is equal to half the diameter of the graph. In particular, the 2-capture time of the m x n grid is proved to be floor ((m+n-2)/2).
Recommendations
Cites work
- scientific article; zbMATH DE number 5241699 (Why is no real title available?)
- A game of cops and robbers played on products of graphs
- A note on \(k\)-cop, \(l\)-robber games on graphs
- Cop-win graphs with maximum capture-time
- Searching and sweeping graphs: a brief survey
- The capture time of a graph
- Vertex-to-vertex pursuit in a graph
Cited in
(20)- Lower bounds for the capture time: linear, quadratic, and beyond
- The game of cops and eternal robbers
- Cops and robbers on geometric graphs
- Capture times in the bridge-burning cops and robbers game
- Cops and robber on butterflies and solid grids
- Linguistic geometry approach for solving the cops and robber problem in grid environments
- The capture time of a planar graph
- On the Capture Time of Cops and Robbers Game on a Planar Graph
- The optimal capture time of the one-cop-moves game
- Cops and robber on butterflies, grids, and AT-free graphs
- Bounds on the length of a game of cops and robbers
- Cops and robber game on infinite chessboard
- Throttling for the game of cops and robbers on graphs
- The game of overprescribed Cops and Robbers played on graphs
- The capture time of the hypercube
- Chasing a drunk robber in many classes of graphs
- Conjectures on cops and robbers
- Police and robber game on infinite chessboard
- A tight lower bound for the capture time of the cops and robbers game
- Some remarks on cops and drunk robbers
This page was built for publication: The capture time of grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616367)
