ArticleOriginal scientific text

Title

Characterizing Cartesian fixers and multipliers

Authors 1, 1

Affiliations

  1. 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ₙ) ≥ 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.

Keywords

Cartesian product, prism fixer, Cartesian fixer, prism doubler, Cartesian multiplier, domination number

Bibliography

  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.
Pages:
161-175
Main language of publication
English
Received
2009-02-26
Accepted
2011-03-15
Published
2012
Exact and natural sciences