# Vizing's conjecture and the one-half argument

Bert Hartnell; Douglas F. Rall

Discussiones Mathematicae Graph Theory (1995)

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

## Access Full Article

top## Abstract

top## How to cite

topBert 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] 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). Zbl0403.05027
- [3] B.L. Hartnell and D.F. Rall, On Vizing's conjecture, Congr. Numer. 82 (1991) 87-96. Zbl0764.05092
- [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] V.G. Vizing, The Cartesian product of graphs, Vyc. Sis. 9 (1963) 30-43.

## Citations in EuDML Documents

top## NotesEmbed ?

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