On Vizing's conjecture

Bostjan Bresar

Discussiones Mathematicae Graph Theory (2001)

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

Abstract

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

How to cite

top

Bostjan 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. [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. [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. [3] M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223-227. Zbl0746.05067
  4. [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. [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. [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. [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. [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. [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. [10] V.G. Vizing, The Cartesian product of graphs, Vycisl. Sist. 9 (1963) 30-43. 

NotesEmbed ?

top

You must be logged in to post comments.