# Vizing's conjecture and the one-half argument

• Volume: 15, Issue: 2, page 205-216
• ISSN: 2083-5892

top

## Abstract

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

## How to cite

top

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 -

## References

top
1. [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. [2] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt International Series, 1979). Zbl0403.05027
3. [3] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. Zbl0764.05092
4. [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. Zbl0584.05053
5. [5] V.G. Vizing, The Cartesian product of graphs, Vyc. Sis. 9 (1963) 30-43.

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.