The Cop, Robber and Decoy game
LE3 .A278 2014
Master of Science
The game of Cops and Robber is a classical pursuit-evasion game played on re exive undirected graphs. The objective of this game is to nd the minimum number of cops su cient to catch the robber. Several variants of the classical Cops and Robber game have been studied. In this thesis, a new variant of the Cops and Robber game \The Cop, Robber and Decoy" is explored. The Cop, Robber and Decoy version of the game is played on copwin graphs where a single cop tries to capture a single robber, but during the game the robber is allowed to throw a decoy to distract the cop. The Cop, Robber and Decoy game has three variants which are explained in detail with possible graph characterization in this thesis. The thesis also focuses on investigating some possible strategies for the cop on bigger graphs without having perfect information about the robber and the decoy.
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.