The game of Cops and Robbers is a pursuit-evasion game played on graphs with two players, the cops and the robber, who take turns moving on the graph. In each turn, they may move to a vertex adjacent to their current position or stay where they are. The cops’ objective is to get to the same position where the robber is, which we refer to as to capture the robber, and the robber’s goal is to evade capture indefinitely. The basic question is to find the minimum number of cops that can guarantee capturing the robber in a given graph. A very fruitful research area has been developed around the idea of modifying the way in which the cops or the robber move and analysing how these changes affect the strategies and outcome of the game. In this thesis we will study the game when we impose additional speed restrictions on the players, variants of the game popularly known as “lazy-cops and robbers” and “active cops and robbers”. In order to do so, we introduce the concept of the wide shadow, aiming to improve known results and obtain new tools and techniques which may provide further insight into other open problems in the area.
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection