Journal of Combinatorics
Volume 12 (2021)
Cops, robbers, and burning bridges
Pages: 515 – 546
We consider a variant of Cops and Robbers wherein each edge traversed by the robber is deleted from the graph. The focus is on determining the minimum number of cops needed to capture a robber on a graph $G$, called the bridge-burning cop number of $G$ and denoted $c_b (G)$. We determine $c_b (G)$ exactly for several elementary classes of graphs and give a polynomial-time algorithm to compute $c_b (T)$ when $T$ is a tree. We also study two-dimensional square grids and tori, as well as hypercubes, and we give bounds on the capture time of a graph (the minimum number of rounds needed for a single cop to capture a robber on $G$, provided that $c_b (G) = 1$).
cops and robbers, pursuit-evasion
2010 Mathematics Subject Classification
Primary 05C57. Secondary 05C85.
Received 29 December 2018
Accepted 11 September 2020
Published 8 November 2021