On Cartesian products having a minimum dominating set that is a box or a stairway
Douglas Rall
Furman University
Bo\v{s}tjan Bre\v{s}ar
University of Maribor \& \\ Institute of Mathematics, Physics and Mechanics
PDF
Minisymposium: GRAPH PRODUCTS
Content: Combining a lower bound due to El-Zahar and Pareek with an upper bound of Vizing we get that for any pair of graphs $G$ and $H$, \[ \min\{|V(G)|,|V(H)|\}\le \gamma(G\,\Box\, H) \le \min \{\gamma(G)|V(H)|, \gamma(H)|V(G)|\}\,.\] We give a complete characterization of the pairs that achieve the lower bound and give some necessary and some sufficient conditions for pairs of graphs that meet the upper bound.