The donut-shop model of cops and robbers

Loading...
Thumbnail Image

Date

2023-08

Journal Title

Journal ISSN

Volume Title

Publisher

University of New Brunswick

Abstract

We explore a variation of the game of Cops and Robbers on graphs, in which cops pursue a robber in the presence of one or more special vertices: donut-shops. The location of a donut-shop is determined before each player selects their starting position, and should a cop ever move to a donut-shop, they cannot move for the remainder of the game. These conditions form the donut-shop model for Cops and Robbers. This thesis introduces the donut-shop cop-number, representing the minimum number of cops needed to capture the robber in this model. We determine the donut-shop cop-number of some classes of graphs, which depends on the vertex on which the donut-shop is established. In particular, we give an upper bound for the donut-shop cop-number of planar graphs. A programmatic implementation of this model is also provided.

Description

Keywords

Citation