Cops and Robber on Some Families of Oriented Graphs

Cops and robber game on a directed graph (D) over right arrow initiates by Player 1 placing k cops and then Player 2 placing one robber on the vertices of (D) over right arrow. After that, starting with Player 1, alternately the players may move each of their tokens to the adjacent vertices. Player 1 wins if, after a finite number of moves, a cop and the robber end up on the same vertex and Player 2 wins otherwise. However, depending on the type of moves the players make, there are three different models, namely, the normal cop model : both cops and robber move along the direction of the arcs; the strong cop model: cops can move along or against the direction of the arcs while the robber moves along them; and the weak cop model: the robber can move along or against the direction of the arcs while the cops move along them. A graph is cop-win if Player 1 playing with a single cop has a winning strategy. In this article, we study the three models on some families of oriented graphs and characterize the cop-win directed graphs for the third model.