Vizing's conjecture and the one-half argument

Bert Hartnell, and Douglas F. Rall. "Vizing's conjecture and the one-half argument." Discussiones Mathematicae Graph Theory 15.2 (1995): 205-216. <http://eudml.org/doc/270671>.

@article{BertHartnell1995,
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, γ(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.},
author = {Bert Hartnell, Douglas F. Rall},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; Cartesian product; Vizing's conjecture; clique; Vising's conjecture; dominating set; partitioning},
language = {eng},
number = {2},
pages = {205-216},
title = {Vizing's conjecture and the one-half argument},
url = {http://eudml.org/doc/270671},
volume = {15},
year = {1995},
}

TY - JOUR
AU - Bert Hartnell
AU - Douglas F. Rall
TI - Vizing's conjecture and the one-half argument
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 2
SP - 205
EP - 216
AB - 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.
LA - eng
KW - domination number; Cartesian product; Vizing's conjecture; clique; Vising's conjecture; dominating set; partitioning
UR - http://eudml.org/doc/270671
ER -