Geodesic
Improving some bounds for dominating Cartesian products
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 261-272

Voir la notice de l'article provenant de la source Library of Science

The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds for dominating the Cartesian product of any two graphs. We show how it is possible to improve some of these bounds by imposing conditions on both graphs. For example, we establish a new lower bound for the domination number of T T, when T is a tree, and we improve an upper bound of Vizing in the case when one of the graphs has k > 1 dominating sets which cover the vertex set and the other has a dominating set which partitions in a certain way.
Keywords: domination number, Cartesian product, Vizing's conjecture, 2-packing 
@article{DMGT_2003_23_2_a4,
     author = {Hartnell, Bert and Rall, Douglas},
     title = {Improving some bounds for dominating {Cartesian} products},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {261--272},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a4/}
}
TY  - JOUR
AU  - Hartnell, Bert
AU  - Rall, Douglas
TI  - Improving some bounds for dominating Cartesian products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 261
EP  - 272
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a4/
LA  - en
ID  - DMGT_2003_23_2_a4
ER  - 
%0 Journal Article
%A Hartnell, Bert
%A Rall, Douglas
%T Improving some bounds for dominating Cartesian products
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 261-272
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a4/
%G en
%F DMGT_2003_23_2_a4
Hartnell, Bert; Rall, Douglas. Improving some bounds for dominating Cartesian products. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 261-272. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a4/