On the characterization of cop-win and robber-win graphs

Date of Publication

2015

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Mathematics with specialization in Business Applications

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Abstract/Summary

Cops and Robbers is a pursuit game where two persons play as a cop and a robber. The objective of the game is for the cop to catch the robber, and for the robber to evade the cop. In this paper, we study Cops and Robbers in graphs. The rules of the game is that the cop player first deploys his unit in a vertex, while the robber, knowing the location of the cop, will place his unit on another vertex. The players take turns in moving their respective units to an adjacent vertex where the robber has the option to stay in his current position while the cop must move towards the robber. We classify a graph G as either cop-win or robber-win by using the concept of pitfalls. A pitfall is a point p in a graph G where there exists another vertex d in G such that the robber's position p, along with its neighborhood, is within the neighborhood of the cop's position d, or N(p) [ fpg N(d). We will also use the concept of dominating rows and columns from Game Theory to determine if Pn C is cop-win or robber-win.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTU021088

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

1 computer disc ; 4 3/4 in.

Keywords

Graph theory; Game theory

Embargo Period

5-11-2021

This document is currently not available here.

Share

COinS