Geodesic
Vizing's conjecture and the one-half argument
Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 205-216 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: domination number, Cartesian product, Vizing's conjecture, clique 
@article{DMGT_1995_15_2_a7,
     author = {Hartnell, Bert and Rall, Douglas},
     title = {Vizing's conjecture and the one-half argument},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {205--216},
     year = {1995},
     volume = {15},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a7/}
}
TY  - JOUR
AU  - Hartnell, Bert
AU  - Rall, Douglas
TI  - Vizing's conjecture and the one-half argument
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1995
SP  - 205
EP  - 216
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a7/
LA  - en
ID  - DMGT_1995_15_2_a7
ER  - 
%0 Journal Article
%A Hartnell, Bert
%A Rall, Douglas
%T Vizing's conjecture and the one-half argument
%J Discussiones Mathematicae. Graph Theory
%D 1995
%P 205-216
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a7/
%G en
%F DMGT_1995_15_2_a7
Hartnell, Bert; Rall, Douglas. Vizing's conjecture and the one-half argument. Discussiones Mathematicae. Graph Theory, Tome 15 (1995) no. 2, pp. 205-216. http://geodesic.mathdoc.fr/item/DMGT_1995_15_2_a7/

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