LE3 .A278 2006

2006

Clarke, Nancy

Acadia University

Master of Science

Masters

Mathematics and Statistics

Mathematics & Statistics

This thesis explores a modified version of the Cops and Robber game, which itself is a discrete version of searching networks. In this version of the game, there are two cops playing with partial information provided by various types of technology. There are two types of information available, that which is provided via devices placed on selected edges of a graph, and that provided via devices placed on selected vertices. Since the information may or may not indicate the robber's direction in addition to his position, the problem can be divided into four cases. The thesis focuses on finding bounds for the amount of such information required by two cops to guarantee the capture of the robber on copwin graphs. Schemes for placing devices on graphs, together with corresponding strategies which the cops need to follow, are given. More localized and much more efficient schemes for placing devices on full complete k-ary trees, where k ¸ 2, are also given. Much work has been done on this problem when only one cop is in pursuit of the robber, which allows for a comparison of the performance of one cop versus that of two cops when playing on the same graph. Finally, another variation of the game is explored, where either one or two cops play with partial information as well as visibility one, which allows the cops to “see” all neighboring vertices. Some preliminary results on searching graphs, particularly trees, are given for one and two cops playing with visibility zero or one.

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:114