×

The capture time of grids. (English) Zbl 1203.91039

Summary: 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\times n\) grid is proved to be \(\lfloor \frac{m+n}{2} \rfloor -1\).

MSC:

91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
05C57 Games on graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alspach, B., Searching and sweeping graphs: a brief survey, Matematiche (Catania), 59, 5-37 (2006) · Zbl 1195.05019
[2] Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J., The capture time of a graph, Discrete Math., 309, 5588-5595 (2009) · Zbl 1177.91056
[3] Gavenčiak, T., Cop-win graphs with maximal capture-time, Discrete Math., 310, 1557-1563 (2010) · Zbl 1186.91051
[4] Hahn, G., Cops, robbers and graphs, Tatra Mt. Math. Publ., 36, 1-14 (2007) · Zbl 1164.05063
[5] Hahn, G.; MacGillivray, G., A note on \(k\)-cop, \(l\)-robber games on graphs, Discrete Math., 306, 2492-2497 (2006) · Zbl 1201.91018
[6] Neufeld, S.; Nowakowski, R., A game of cops and robbers played on products of graphs, Discrete Math., 186, 253-268 (1998) · Zbl 0957.91029
[7] Nowakowski, R.; Winkler, P., Vertex to vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058
[8] A. Quilliot, Jeux et pointes fixes sur les graphes, Ph.D. Dissertation, Université de Paris VI, 1978.; A. Quilliot, Jeux et pointes fixes sur les graphes, Ph.D. Dissertation, Université de Paris VI, 1978.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.