DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 15(2) (1995) 205-216
DOI: 10.7151/dmgt.1018

VIZING'S CONJECTURE AND THE ONE-HALF ARGUMENT

Bert Hartnell

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

Douglas F. Rall

Furman University, Greenville,
SC 29613, U.S.A.

Abstract

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, γ(GH)≥γ(G)γ(H),  where GH 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.

Keywords: domination number, Cartesian product, Vizing's conjecture, clique.

1991 Mathematics Subject Classification: 05C70, 05C99.

References

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