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

• Main Authors: Chua, Jian Christian E., Sevilla, Antonio Lorenzo M.
• Format: text
• Language: English
• Published: Animo Repository 2015
• Subjects: Graph theory; Game theory; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/14915
• Institution: De La Salle University

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.