Watchman's walk on products
Thamalikha Dissanayake Mudiyanselage · 2025
The watchman's walk problem is concerned with finding a shortest walk through a museum, starting and ending at the same point, such that such that a guard either visits or peers into every room. That is fi nding a minimum closed dominating walk. The length of this walk is the watchman number. In this work, we study the watchman number of the strong, categorical and lexicographic products of graphs. For the strong product we study the watchman's walk of arbitrary graphs, cycles and we give several bounds. We also consider the watchman's walk for the categorical product of graphs and we discuss some families of graphs such as complete graphs and cycles. We also give upper bounds for the watchman number of arbitrary graphs. Finally, we consider the lexicographic product and we completely characterize the watchman number.