Game of Cops and Robbers on Eulerian Digraphs

Cops and Robbers is a well-known pursuit game played on a graph. There are two players, one controls the cops and the other controls the robber, who take turns moving along edges of the graph. The goal of the cops is to capture the robber, which is accomplished if a cop occupies the same vertex as the robber. The main question is to determine the minimum number of cops that can guarantee the robber’s capture on the given graph. This problem has been widely studied for the case of undirected graphs, but very little attention has been given to finding the cop number of digraphs. In the thesis we focus on this game on Eulerian digraphs, viewed as an extension of the game on undirected graphs. Some preliminary results, which were obtained for the special case of 4-regular quadrangulations of the torus and the Klein bottle, show that there is a possibility to develop rich results in this area.