A domination Algorithm for Generalized Cartesian Products

Let \( G \, \Box \, H \) denote the Cartesian product of two graphs \( G \) and \( H \). In 1994, Livingston and Stout [Constant time computation of minimum dominating sets, Congr. Numer., 105 (1994), 116-128] introduced a linear time algorithm to determine \( \gamma(G \, \Box \, P_n) \) for fixed \( G \), and claimed that \( P_n \) may be substituted with any graph from a one-parameter family, such as a cycle of length \( n \) or a complete \( t \)-ary tree of height \( n \) for fixed \( t \). We explore how the algorithm may be modified to accommodate such graphs and propose a general framework to determine \( \gamma(G \, \Box \, H) \) for any graph \( H \). Furthermore, we illustrate its use in determining the domination number of the generalized Cartesian product \( G \, \Box \, H \), as defined by Benecke and Mynhardt [Domination of Generalized Cartesian Products, preprint (2009)].