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ₙ) ≥ min{|V(G)|, γ(G)+n-2}. We call a graph G a consistent fixer if γ(G ☐ Kₙ) = γ(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γ(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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1594,
author = {Stephen Benecke and Christina M. Mynhardt},
title = {Characterizing Cartesian fixers and multipliers},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {161-175},
zbl = {1255.05163},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1594}
}
Stephen Benecke; Christina M. Mynhardt. Characterizing Cartesian fixers and multipliers. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 161-175. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1594/
[000] [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. | Zbl 1064.05111
[001] [2] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincaré Sect. B (N.S.) 3 (1967) 433-438. | Zbl 0162.27605
[002] [3] B.L. Hartnell and D.F. Rall, Lower bounds for dominating Cartesian products, J. Combin. Math. Combin. Comput. 31 (1999) 219-226. | Zbl 0938.05048
[003] [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. | Zbl 1063.05107
[004] [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[005] [6] C.M. Mynhardt and Z. Xu, Domination in prisms of graphs: Universal fixers, Utilitas Math. 78 (2009) 185-201. | Zbl 1284.05199