Minimum dominating walks in Cartesian product graphs

Abstract

A dominating walk W in a graph G is a walk such that for each v ∈ V(G), either v ∈ V(W) or v is adjacent to a vertex of W. A minimum closed dominating walk (MCDW) is a dominating walk of shortest length that starts and ends at the same point. In this study we obtain sharp bounds on the length of a MCDW in the Cartesian product T × K_n, for n ≥ 2, where T is a tree. In the case when n = 2, we characterize the trees in which the lower bound is achieved and construct an infinite family of trees in which the upper bound is achieved.