Some problems on the game of ambush cops and robbers
LE3 .A278 2019
Master of Science
Mathematics & Statistics
This thesis considers a variation of the game of Cops and Robber played on graphs. In this variation, known as Ambush Cops and Robbers, the robber is given an accomplice with whom he can eliminate a cop under certain circumstances. Our objective is to minimize the number of pursuers that can capture one of the robbers without losing one of their number. Several classes of graphs are considered including outerplanargraphs, chordal graphs, and various graph products. We then consider the game of Ambush Cops and Robbers played with partial information. In that case, the cop may only obtain information about the robbers’ positions on the graph through certain devices located on the elements of said graph. The placement of these devices is incorporated in his winning strategy. We seek to minimize the number of devices placed on the graphs without compromising the cop’s ability to safely capture a robber.
The author grants permission to the University Librarian at Acadia University to reproduce, loan or distribute copies of my thesis in microform, paper or electronic formats on a non-profit basis. The author retains the copyright of the thesis.