Vizing's conjecture and the one-half argument

• Autorzy: Bert Hartnell , Douglas F. Rall
• 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.

Słowa kluczowe

EN

domination number   Cartesian product   Vizing's conjecture   clique  

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C99: None of the above, but in this section

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 2
• Strony: 205-216

Daty

wydano

1995

otrzymano

1995-05-25

Twórcy

autor

Bert Hartnell

• Saint Mary's University, Halifax, Nova Scotia, Canada B3H 3C3

autor

Douglas F. Rall

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

Identyfikatory

DOI

10.7151/dmgt.1018