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.

Back to all abstracts