The capture time of grids

DOI10.1016/J.DISC.2010.10.002zbMATH Open1203.91039arXiv1008.4424OpenAlexW2171304259MaRDI QIDQ616367FDOQ616367

Authors: Abbas Mehrabian 

Publication date: 7 January 2011

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

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).

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

Recommendations

• The capture time of a graph
• The game of overprescribed Cops and Robbers played on graphs
• Bounds on the length of a game of cops and robbers
• Catching an infinitely fast robber on a grid
• scientific article; zbMATH DE number 5989957

zbMATH Keywords

gridscops and robber gameCartesian productscapture time

Mathematics Subject Classification ID

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

Cites Work

• The capture time of a graph
• Vertex-to-vertex pursuit in a graph
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Cop-win graphs with maximum capture-time
• A game of cops and robbers played on products of graphs
• Searching and sweeping graphs: a brief survey
• Title not available (Why is that?)

Cited In (20)

• The optimal capture time of the one-cop-moves game
• Chasing a drunk robber in many classes of graphs
• Cops and robber on butterflies, grids, and AT-free graphs
• The game of cops and eternal robbers
• A tight lower bound for the capture time of the cops and robbers game
• The capture time of a planar graph
• Throttling for the game of cops and robbers on graphs
• Title not available (Why is that?)
• Capture times in the bridge-burning cops and robbers game
• Some remarks on cops and drunk robbers
• Bounds on the length of a game of cops and robbers
• Conjectures on Cops and Robbers
• Cops and robber on butterflies and solid grids
• Lower bounds for the capture time: linear, quadratic, and beyond
• Cops and robber game on infinite chessboard
• The capture time of the hypercube
• Linguistic geometry approach for solving the cops and robber problem in grid environments
• The game of overprescribed Cops and Robbers played on graphs
• Cops and robbers on geometric graphs
• On the Capture Time of Cops and Robbers Game on a Planar Graph

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)