Game of Cops and Robbers on Eulerian Digraphs

Resource type
Thesis type
(Thesis) Ph.D.
Date created
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.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Thesis advisor: Goddyn, Luis
Member of collection
Download file Size
etd10651_SHosseini.pdf 821.37 KB

Views & downloads - as of June 2023

Views: 20
Downloads: 0