Efficient Cartesian Product Layer Domination
by
Robert Rubalcaba
Department of Defense
Coauthors: Peter J. Slater (University of Alabama in Huntsville)

Let G×H denote the Cartesian product of G with H. For each h ∈ V(H), G ×{h} is a copy of G called a G-layer (or G-fiber) of G×H. Similarly, for each g ∈ V(G), {g}×H is a copy of H called a H-layer (or H-fiber). An efficient dominating set in G×H is a dominating set D ⊆ V(G×H) with |D∩N[v]|=1 for all v ∈ V(G×H).

A minimum dominating set D ⊆ V(G×H) is G-layer (Cartesian product) efficient if for all v ∈ { < G ×{h} > - N[D|_{G ×{h}}] } we have |N[v]∩D|=1, for all h ∈ V(H). That is, all vertices not dominated by their own G-layer are dominated exactly once by a vertex in another G-layer. Clearly, any efficient dominating set is both G-layer and H-layer efficient, however, the converse need not be true. We give examples of product graphs which have no G-layer efficient dominating set. We also present product graphs which are G-layer efficient for any graph H.

Date received: April 12, 2009