Journal of Combinatorics

Volume 12 (2021)

Number 3

Cops, robbers, and burning bridges

Pages: 515 – 546

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n3.a5

Authors

William B. Kinnersley (Department of Mathematics, University of Rhode Island, Kingston, R.I., U.S.A.)

Eric Peterson (Department of Mathematics, University of Rhode Island, Kingston, R.I., U.S.A.)

Abstract

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

Keywords

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