Geodesic
A New Framework to Approach Vizing’s Conjecture
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 749-762.

Voir la notice de l'article provenant de la source Library of Science

We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing’s conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: γ (X □ Y) ≥max{1/2γ (X) γ_t (Y), 1/2γ_t (X) γ (Y) }, where γ stands for the domination number, γ_t is the total domination number, and X □ Y is the Cartesian product of graphs X and Y.
Keywords: Cartesian product, total domination, Vizing’s conjecture, Clark and Suen bound 
@article{DMGT_2021_41_3_a3,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Hartnell, Bert L. and Henning, Michael A. and Kuenzel, Kirsti and Rall, Douglas F.},
     title = {A {New} {Framework} to {Approach} {Vizing{\textquoteright}s} {Conjecture}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {749--762},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a3/}
}
TY  - JOUR
AU  - Brešar, Boštjan
AU  - Hartnell, Bert L.
AU  - Henning, Michael A.
AU  - Kuenzel, Kirsti
AU  - Rall, Douglas F.
TI  - A New Framework to Approach Vizing’s Conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 749
EP  - 762
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a3/
LA  - en
ID  - DMGT_2021_41_3_a3
ER  - 
%0 Journal Article
%A Brešar, Boštjan
%A Hartnell, Bert L.
%A Henning, Michael A.
%A Kuenzel, Kirsti
%A Rall, Douglas F.
%T A New Framework to Approach Vizing’s Conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 749-762
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a3/
%G en
%F DMGT_2021_41_3_a3
Brešar, Boštjan; Hartnell, Bert L.; Henning, Michael A.; Kuenzel, Kirsti; Rall, Douglas F. A New Framework to Approach Vizing’s Conjecture. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 749-762. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a3/

[1] R. Aharoni and T. Szabó, Vizing’s conjecture for chordal graphs, Discrete Math. 309 (2009) 1766–1768. doi:10.1016/j.disc.2008.02.025

[2] A.M. Barcalkin and L.F. German, The external stability number of the Cartesian product of graphs, Bul. Akad. Stiinte RSS Moldoven. 94 (1979) 5–8.

[3] B. Brešar, Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs, Discrete Math. 340 (2017) 2398–2401. doi:10.1016/j.disc.2017.05.007

[4] B. Brešar, Vizing’s conjecture for graphs with domination number 3 —a new proof, Electron. J. Combin. 22(3) (2015) #P3.38.

[5] B. Brešar, P. Dorbec, W. Goddard, B.L. Hartnell, M.A. Henning, S. Klavžar and D.F. Rall, Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012) 46–76. doi:10.1002/jgt.20565

[6] B. Brešar and D.F. Rall, Fair reception and Vizing’s conjecture, J. Graph Theory 61 (2009) 45–54. doi:10.1002/jgt.20366

[7] W.E. Clark and S. Suen, An inequality related to Vizing’s conjecture, Electron. J. Combin. 7 (2000) #N4.

[8] P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960) 17–61.

[9] B.L. Hartnell and D.F. Rall, Vizing’s conjecture and the one-half argument, Discuss. Math. Graph Theory 15 (1995) 205–216. doi:10.7151/dmgt.1018

[10] J.W. Moon and L. Moser, Almost all (0, 1) matrices are primitive, Studia Sci. Math. Hungar. 1 (1966) 153–156.

[11] M. Pilipczuk, M. Pilipczuk and R. Škrekovski, Some results on Vizing’s conjecture and related problems, Discrete Appl. Math. 160 (2012) 2484–2490. doi:10.1016/j.dam.2012.06.011

[12] S. Suen and J. Tarr, An improved inequality related to Vizing’s conjecture, Electron. J. Combin. 19(1) (2012) #P8.

[13] L. Sun, A result on Vizing’s conjecture, Discrete Math. 275 (2004) 363–366. doi:10.1016/j.disc.2003.09.003

[14] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23(6) (1968) 125–141. doi:10.1070/RM1968v023n06ABEH001252

[15] S. Zerbib, An improved bound in Vizing’s Conjecture, Graphs Combin. 35 (2019) 1401–1404. doi:/10.1007/s00373-019-02083-6