On dominating the Cartesian product of a graph and K₂

Bert L. Hartnell; Douglas F. Rall

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 389-402
  • ISSN: 2083-5892

Abstract

top
In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated further.

How to cite

top

Bert L. Hartnell, and Douglas F. Rall. "On dominating the Cartesian product of a graph and K₂." Discussiones Mathematicae Graph Theory 24.3 (2004): 389-402. <http://eudml.org/doc/270156>.

@article{BertL2004,
abstract = {In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated further.},
author = {Bert L. Hartnell, Douglas F. Rall},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; 2-packing, Cartesian product; domination number},
language = {eng},
number = {3},
pages = {389-402},
title = {On dominating the Cartesian product of a graph and K₂},
url = {http://eudml.org/doc/270156},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Bert L. Hartnell
AU - Douglas F. Rall
TI - On dominating the Cartesian product of a graph and K₂
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 389
EP - 402
AB - In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated further.
LA - eng
KW - domination; 2-packing, Cartesian product; domination number
UR - http://eudml.org/doc/270156
ER -

References

top
  1. [1] W.E. Clark and S. Suen, An inequality related to Vizing's conjecture, Elec. J. of Comb. 7 (#N4) (2000) 1-3. Zbl0947.05056
  2. [2] M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223-227. Zbl0746.05067
  3. [3] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. Zbl0764.05092
  4. [4] B.L. Hartnell and D.F. Rall, Lower bounds for dominating Cartesian products, J. Comb. Math. Comb. Comp. 31 (1999) 219-226. Zbl0938.05048
  5. [5] B.L. Hartnell and D.F. Rall, Improving some bounds for dominating Cartesian products, Discuss. Math. Graph Theory 23 (2003) 261-272, doi: 10.7151/dmgt.1201. Zbl1055.05115
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 208, Marcel Dekker, Inc., New York, 1998. Zbl0890.05002
  7. [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 209, Marcel Dekker, Inc., New York, 1998. Zbl0883.00011
  8. [8] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 2000. 
  9. [9] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars Combin. 18 (1983) 33-44. Zbl0566.05050
  10. [10] M.S. Jacobson and L.F. Kinch, On the domination of the products of graphs II: trees, J. Graph Theory 10 (1986) 97-106, doi: 10.1002/jgt.3190100112. Zbl0584.05053
  11. [11] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy 9 (1963) 30-43. 
  12. [12] V.G. Vizing, Some unsolved problems in graph theory, Uspehi Mat. Nauk 23 no. 6(144) (1968) 117-134. Zbl0177.52301

Citations in EuDML Documents

top
  1. Michel Mollard, On the Domination of Cartesian Product of Directed Cycles: Results for Certain Equivalence Classes of Lengths
  2. Seyyed Mahmoud Sheikholeslami, Lutz Volkmann, The k-rainbow domatic number of a graph
  3. Kirsti Wash, Edgeless graphs are the only universal fixers
  4. Christina M. Mynhardt, Mark Schurch, Paired domination in prisms of graphs
  5. Richard G. Gibson, Christina M. Mynhardt, Counterexample to a conjecture on the structure of bipartite partitionable graphs
  6. Stephen Benecke, Christina M. Mynhardt, Characterizing Cartesian fixers and multipliers
  7. Linda Eroh, Ralucca Gera, Cong X. Kang, Craig E. Larson, Eunjeong Yi, Domination in functigraphs

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.