The deduction model for Cops and Robber

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

[img] [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)


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.

Item Type: Thesis (Masters)
Item ID: 15549
Additional Information: Includes bibliographical references (pages 70-71).
Keywords: graph searching, Cops and Robbers
Department(s): Science, Faculty of > Mathematics and Statistics
Date: May 2022
Date Type: Submission
Digital Object Identifier (DOI):
Library of Congress Subject Heading: Graph theory; Game theory; Games of strategy (Mathematics).

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics