Cops, robbers, and barricades

Cops, Robbers, and Barricades is a new variant of the game on graphs, Cops and Robbers. In this variant, the robber may build barricades that restrict the movements of the cops. The minimum number of cops required to capture the robber on a graph G is called the barricade-cop number, denoted cB(G). If cB(G) = 1, then G is called barricade-cop-win. The game can be generalized so that the robber may build b(k)-many barricades on vertices during her kth turn, in accordance with barricade rules that dictate the permissible positions of these barricades. The barricade-cop number is determined exactly for complete graphs, cycles, and paths, and we provide bounds on trees and locally-path-like graphs. We compare and contrast variants on the barricade rules, and give an algorithmic characterization of barricade-cop-win graphs with any set of barricade rules.