PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1995 | 15 | 2 | 205-216
Tytuł artykułu

Vizing's conjecture and the one-half argument

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as well as the collection of graphs considered by Barcalkin and German in [1]. A crucial part of the proof depends on the well-known fact that the domination number of any connected graph of order at least two is no more than half its order.
Wydawca
Rocznik
Tom
15
Numer
2
Strony
205-216
Opis fizyczny
Daty
wydano
1995
otrzymano
1995-05-25
Twórcy
  • Saint Mary's University, Halifax, Nova Scotia, Canada B3H 3C3
  • Furman University, Greenville, SC 29613, U.S.A.
Bibliografia
  • [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] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt International Series, 1979).
  • [3] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96.
  • [4] 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.
  • [5] V.G. Vizing, The Cartesian product of graphs, Vyc. Sis. 9 (1963) 30-43.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1018
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.