LE3 .A278 2013

2013

Clarke, Nancy

Acadia University

Bachelor of Science

Honours

Mathematics and Statistics

Mathematics & Statistics

The Cops and Robber game is a discrete time vertex-to-vertex pursuit game played on some graph, G. The original game is played with one cop, one robber and perfect information. This thesis examines a modi ed version of the Cops and Robber game with partial information and k cops. The information is provided by two types of devices, those placed on vertices and those placed on edges. The information de- vices can either provide the direction of the robber or not, allowing us to partition the problem into four cases. The main focus of this thesis is to x the amount of information provided and determine the number of cops required to apprehend the robber. We will focus primarily on a speci c class of graphs, grids. A new strategy for placing the information devices is developed and bounds on the number of cops are given for each of the four cases. In the fourth section, we look at the problem from the opposite perspective; we x the number of cops at one and determine the information required for the robber to be apprehended. A new strategy is developed which improves the bounds on the amount of information needed for full complete k-ary trees with one cop.

The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.

https://scholar.acadiau.ca/islandora/object/theses:942