# On Vizing's conjecture

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 1, page 5-11
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBostjan Bresar. "On Vizing's conjecture." Discussiones Mathematicae Graph Theory 21.1 (2001): 5-11. <http://eudml.org/doc/270337>.

@article{BostjanBresar2001,

abstract = {A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.},

author = {Bostjan Bresar},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; Cartesian product; domination number},

language = {eng},

number = {1},

pages = {5-11},

title = {On Vizing's conjecture},

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

volume = {21},

year = {2001},

}

TY - JOUR

AU - Bostjan Bresar

TI - On Vizing's conjecture

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 1

SP - 5

EP - 11

AB - A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.

LA - eng

KW - graph; Cartesian product; domination number

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

ER -

## References

top- [1] A.M. Barcalkin and L.F. German, The external stability number of the Cartesian product of graphs, Bul. Acad. Stiinte RSS Moldovenesti 1 (1979) 5-8.
- [2] T.Y. Chang and W.Y. Clark, The domination number of the 5×n and 6×n grid graphs, J. Graph Theory 17 (1993) 81-107, doi: 10.1002/jgt.3190170110. Zbl0780.05030
- [3] M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223-227. Zbl0746.05067
- [4] R.J. Faudree, R.H. Schelp, W.E. Shreve, The domination number for the product of graphs, Congr. Numer. 79 (1990) 29-33. Zbl0862.05060
- [5] D.C. Fisher, Domination, fractional domination, 2-packing, and graph products, SIAM J. Discrete Math. 7 (1994) 493-498, doi: 10.1137/S0895480191217806. Zbl0812.05030
- [6] B. Hartnell and D.F. Rall, Vizing's conjecture and the one-half argument, Discuss. Math. Graph Theory 15 (1995) 205-216, doi: 10.7151/dmgt.1018. Zbl0845.05074
- [7] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs I, Ars Combin. 18 (1983) 33-44. Zbl0566.05050
- [8] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs II: Trees, J. Graph Theory 10 (1986) 97-106, doi: 10.1002/jgt.3190100112. Zbl0584.05053
- [9] S. Klavžar and N. Seifter, Dominating Cartesian product of cycles, Discrete Appl. Math. 59 (1995) 129-136, doi: 10.1016/0166-218X(93)E0167-W. Zbl0824.05037
- [10] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sist. 9 (1963) 30-43.

## NotesEmbed ?

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