Minimum Dominating Walks in Cartesian Product Graphs
by
Bert Hartnell
Saint Mary's University
Coauthors: Carol Whitehead (Goldsmiths, University of London)

Consider the problem of a security firm that is asked to provide protection for a business by monitoring on a regular basis each node of a network. Each point of interest must either be visited or seen from a neighbouring point by a watchman but this need not be on a continuous basis. The security firm may either want to minimize the length of the watchman's walk or the length of time that nodes are left unguarded. Here we will consider this problem where the network is the cartesian product of a tree with the complete graph.

Date received: April 11, 2001