The watchman's walk problem on directed graphs

Pittman, Brittany (2020) The watchman's walk problem on directed graphs. Masters thesis, Memorial University of Newfoundland.

[img] [English] PDF - Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.

Download (465kB)


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.

Item Type: Thesis (Masters)
Item ID: 14628
Additional Information: Includes bibliographical references (pages 54-55).
Keywords: Graph Theory, Digraphs
Department(s): Science, Faculty of > Mathematics and Statistics
Date: July 2020
Date Type: Submission
Library of Congress Subject Heading: Directed graphs.

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics