Discussiones Mathematicae Graph Theory 32(1) (2012)
161-175

doi: 10.7151/dmgt.1594

## Characterizing Cartesian Fixers and Multipliers

Stephen Benecke and Christina M. Mynhardt
Department of Mathematics and Statistics University of Victoria, P.O. Box 3060 STN CSC Victoria, B.C., Canada V8W 3R4 |

## Abstract

Let G☐ H denote the Cartesian product of the graphs G and H. In
2004, Hartnell and Rall [On dominating the Cartesian product of a graph and
K_{2}, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized
prism fixers, i.e., graphs G for which γ(G☐ K_{2}) = γ(G),
and noted that γ(G☐ K_{n}) ≥ min{ |V(G) |, γ(G)+n−2}. We
call a graph G a consistent fixer if γ(G☐ K_{n}) = γ(G)+n−2
for each n such that 2 ≤ n < |V(G) |− γ(G)+2, and characterize this
class of graphs.
Also in 2004, Burger, Mynhardt and Weakley [On the domination number of prisms
of graphs, Dicuss. Math. Graph Theory **24**(2) (2004), 303-318]
characterized prism doublers, i.e., graphs G for which γ(G☐K_{2}) = 2 γ(G). In general γ(G☐ K_{n}) ≤ n γ(G) for any
n ≥ 2. We call a graph attaining equality in this bound a Cartesian
n-multiplier and also characterize this class of graphs.

**Keywords:** Cartesian product, prism fixer, Cartesian fixer, prism doubler, Cartesian multiplier, domination number

**2010 Mathematics Subject Classification:** 05C69, 05C99.

## References

[1] | A.P. Burger, C.M. Mynhardt and W.D. Weakley, * On the domination number of prisms of graphs*, Dicuss. Math. Graph Theory **24** (2004) 303--318, doi: 10.7151/dmgt.1233. |

[2] | G. Chartrand and F. Harary, * Planar permutation graphs*, Ann. Inst. H. Poincaré Sect. B (N.S.) **3** (1967) 433--438. |

[3] | B.L. Hartnell and D.F. Rall, * Lower bounds for dominating Cartesian products*, J. Combin. Math. Combin. Comput. **31** (1999) 219--226. |

[4] | B.L. Hartnell and D.F. Rall, * On dominating the Cartesian product of a graph and **K*_{2}, Discuss. Math. Graph Theory **24** (2004) 389--402, doi: 10.7151/dmgt.1238. |

[5] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). |

[6] | C.M. Mynhardt and Z. Xu, * Domination in prisms of graphs: Universal fixers*, Utilitas Math. **78** (2009) 185--201. |

Received 26 February 2009

Revised 15 March 2011

Accepted 4 April 2011