# Improving some bounds for dominating Cartesian products

Bert L. Hartnell; Douglas F. Rall

Discussiones Mathematicae Graph Theory (2003)

- Volume: 23, Issue: 2, page 261-272
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBert L. Hartnell, and Douglas F. Rall. "Improving some bounds for dominating Cartesian products." Discussiones Mathematicae Graph Theory 23.2 (2003): 261-272. <http://eudml.org/doc/270360>.

@article{BertL2003,

abstract = {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.},

author = {Bert L. Hartnell, Douglas F. Rall},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination number; Cartesian product; Vizing's conjecture; 2-packing; domination},

language = {eng},

number = {2},

pages = {261-272},

title = {Improving some bounds for dominating Cartesian products},

url = {http://eudml.org/doc/270360},

volume = {23},

year = {2003},

}

TY - JOUR

AU - Bert L. Hartnell

AU - Douglas F. Rall

TI - Improving some bounds for dominating Cartesian products

JO - Discussiones Mathematicae Graph Theory

PY - 2003

VL - 23

IS - 2

SP - 261

EP - 272

AB - 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.

LA - eng

KW - domination number; Cartesian product; Vizing's conjecture; 2-packing; domination

UR - http://eudml.org/doc/270360

ER -

## References

top- [1] A.M. Barcalkin and L.F. German, The external stability number of the Cartesian product of graphs, Bul. Akad. Stiince RSS Moldoven. 1 (1979) 5-8.
- [2] W.E. Clark and S. Suen, An inequality related to Vizing's conjecture, Elec. J. Combin. 7 (#N4) (2000) 1-3. Zbl0947.05056
- [3] M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223-227. Zbl0746.05067
- [4] B.L. Hartnell, On determining the 2-packing and domination numbers of the Cartesian product of certain graphs, Ars Combin. 55 (2000) 25-31. Zbl0994.05102
- [5] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. Zbl0764.05092
- [6] B.L. Hartnell and D.F. Rall, Chapter 7: Domination in Cartesian products: Vizing's conjecture, in: T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 209 (Marcel Dekker, Inc., New York, 1998). Zbl0890.05035
- [7] B.L. Hartnell and D.F. Rall, Lower bounds for dominating Cartesian products, J. Combin. Math. Combin. Comp. 31 (1999) 219-226. Zbl0938.05048
- [8] 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
- [9] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079. Zbl0602.05043
- [10] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars Combin. 18 (1983) 33-44. Zbl0566.05050
- [11] 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
- [12] V.G. Vizing, The Cartesian product of graphs, Vy cisl. Sistemy 9 (1963) 30-43.
- [13] V.G. Vizing, Some unsolved problems in graph theory, Uspehi Mat. Nauk 23 (6) (1968) 117-134. Zbl0177.52301

## Citations in EuDML Documents

top## NotesEmbed ?

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