The watchman's walk problem on directed graphs

Abstract

A watchman’s walk in a graph is a minimum closed dominating walk. Given a graph and a single watchman, the aim of the Watchman’s walk problem is to find a shortest closed walk that allows the guard to efficiently monitor all vertices in the graph. In a directed graph, a watchman’s walk must obey the direction of the arcs. In this case, we say that the guard can only move to and see the vertices that are adjacent to him relative to outgoing arcs. In this thesis, we consider the watchman’s walk problem on directed graphs. In particular, we study the problem on tournaments, orientations of complete bipartite and multipartite graphs, and directed graphs formed from sequences.