The deduction model for Cops and Robber

Abstract

A variation of the game of cops and robber on graphs is studied in which the cops must capture an invisible robber in one move. Cops know each others’ initial locations, but they can only communicate if they are on the same vertex. Thus, the challenge for the cops is to deduce the other cops’ movement and move accordingly in order to capture the robber. This game is called the deduction model for cops and robber. In this thesis, the deduction number is introduced as the minimum number of cops needed to capture the robber in this model. For some classes of graphs, the deduction number is determined. We study the deduction number of trees and provide an upper bound for the Cartesian product of graphs. In particular, we give the deduction number for the hypercubes.