Cops and Robber on Some Families of Oriented Graphs
2019
Cops and robber game on a directed graph \(\overrightarrow{D}\) initiates by Player 1 placing k cops and then Player 2 placing one robber on the vertices of \(\overrightarrow{D}\). 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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
26
References
0
Citations
NaN
KQI