Research Projects

The game of cops and robber is a pursuit evasion game played on a connected graph between two teams, one consisting of cops and the other a single robber. The game involves cops placed on vertices, the robber choosing a vertex, and the cops and robber moving in alternate turns. The cops aim to capture the robber, while the robber aims to avoid being captured. The cops win if they capture the robber in finite turns, while the robber wins if they capture the robber in infinite turns. The minimum number of cops required to capture the robber is the cop number of the graph. Meyniel's conjecture states that the cop number of any graph G on n vertices is O(√n). Variations of the game have been defined based on the abilities of the cops and robber, and the cop number on different variants can be defined. This project aims to obtain bounds on the cop number of graphs in non-trivial graph classes for different variants of the game of cops and robber.