The deduction model for Cops and Robber

Farahani, Mozhgan (2022) The deduction model for Cops and Robber. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (12MB)

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.

Actions (login required)

View Item