The Watchman Problem and the Cartesian Product
Presented by Dr. Bert HARTNELL
Type: Oral presentation
Track: Domination, Independence and Coloring of Product Graphs
Although it would be ideal for a company or security firm to have all nodes in a network monitored at all times (by a person or sensor either at the node itself or adjacent) this may well be too expensive. This gives rise to the watchman problem where a person traverses the graph (returning to the starting point) in such a way that every node is either in this closed walk or adjacent to it. In the most general situation, given a network G and an integer t, we would like to determine the minimum number of watchmen required, and their rounds, so that the maximum time that any node is not monitored (i.e., no watchman in its closed neighbourhood) is t. In a previous investigation, the optimal walk for one watchman in the cartesian product of a tree and a complete graph was considered. We review the problem and indicate very preliminary observations on many watchmen and t=1 in the cartesian product.