DMGT

Discussiones Mathematicae Graph Theory 32(1) (2012) 161-175
DOI: https://doi.org/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₂, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized prism fixers, i.e., graphs G for which γ(G☐ K₂) = γ(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 γ(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₂, 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