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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1238,
author = {Bert L. Hartnell and Douglas F. Rall},
title = {On dominating the Cartesian product of a graph and K2},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {389-402},
zbl = {1063.05107},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1238}
}
Bert L. Hartnell; Douglas F. Rall. On dominating the Cartesian product of a graph and K₂. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 389-402. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1238/
[000] [1] W.E. Clark and S. Suen, An inequality related to Vizing's conjecture, Elec. J. of Comb. 7 (#N4) (2000) 1-3. | Zbl 0947.05056
[001] [2] M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223-227. | Zbl 0746.05067
[002] [3] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. | Zbl 0764.05092
[003] [4] B.L. Hartnell and D.F. Rall, Lower bounds for dominating Cartesian products, J. Comb. Math. Comb. Comp. 31 (1999) 219-226. | Zbl 0938.05048
[004] [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. | Zbl 1055.05115
[005] [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. | Zbl 0890.05002
[006] [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. | Zbl 0883.00011
[007] [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.
[008] [9] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars Combin. 18 (1983) 33-44. | Zbl 0566.05050
[009] [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. | Zbl 0584.05053
[010] [11] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy 9 (1963) 30-43.
[011] [12] V.G. Vizing, Some unsolved problems in graph theory, Uspehi Mat. Nauk 23 no. 6(144) (1968) 117-134. | Zbl 0177.52301