ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 15(2) (1995)
205-216 DOI: 10.7151/dmgt.1018
Saint Mary's University, Halifax,
Nova Scotia, Canada B3H 3C3
Douglas F. Rall
Furman University, Greenville,
SC 29613, U.S.A.
The domination number of a graph G is the smallest order, γ(G),
of a dominating set for G. A conjecture of V. G. Vizing  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 . 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.