Bounds on Watching and Watching Graph Products

Abstract

A watchman’s walk for a graph G is a minimum-length closed dominating walk, and the length of such a walk is denoted (G). We introduce several lower bounds for such walks, and apply them to determine the length of watchman’s walks in several grids.

Keywords

• watchman’s walk
• domination
• graph products
• 05c69