A domination Algorithm for Generalized Cartesian Products

Abstract

Let $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}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\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{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\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)$ for any graph $H$. Furthermore, we illustrate its use in determining the domination number of the generalized Cartesian product $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H$, as defined by Benecke and Mynhardt [Domination of Generalized Cartesian Products, preprint (2009)].