×

zbMATH — the first resource for mathematics

Vizing’s conjecture: a survey and recent results. (English) Zbl 1234.05173
Summary: Vizing’s conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aharoni, A tree version of König’s theorem, Combinatorica 22 (3) pp 335– (2002) · Zbl 1012.05128 · doi:10.1007/s004930200016
[2] Aharoni, Vizing’s conjecture for chordal graphs, Discrete Math 309 (6) pp 1766– (2009) · Zbl 1211.05098 · doi:10.1016/j.disc.2008.02.025
[3] Arnautov, Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices, Prikl Mat i Programmirovanie 126 (11) pp 3– (1974)
[4] Barcalkin, The external stability number of the Cartesian product of graphs, Bul Akad Stiinte RSS Moldoven 94 (1) pp 5– (1979)
[5] Brešar, On Vizing’s conjecture, Discuss Math Graph Theory 21 (1) pp 5– (2001) · Zbl 0989.05084 · doi:10.7151/dmgt.1129
[6] Brešar, Vizing-like conjecture for the upper domination of Cartesian products of graphs-the proof, Electron J Combin 12 (2005)
[7] Brešar, On integer domination in graphs and Vizing-like problems, Taiwanese J Math 10 (5) pp 1317– (2006)
[8] Brešar, Paired-domination of Cartesian products of graphs, Util Math 73 pp 255– (2007)
[9] Brešar, Rainbow domination in graphs, Taiwanese J Math 12 (1) pp 213– (2008)
[10] Brešar, Fair reception and Vizing’s conjecture, J Graph Theory 61 pp 45– (2009) · Zbl 1179.05080 · doi:10.1002/jgt.20366
[11] Burton, Domination dot-critical graphs, Discrete Math 306 (1) pp 11– (2006) · Zbl 1085.05047 · doi:10.1016/j.disc.2005.06.029
[12] Chen, A partition approach to Vizing’s conjecture, J Graph Theory 21 (1) pp 103– (1996) · Zbl 0838.05067 · doi:10.1002/(SICI)1097-0118(199601)21:1<103::AID-JGT13>3.0.CO;2-M
[13] Clark, Application of upper and lower bounds for the domination number to Vizing’s conjecture, Ars Combin 69 pp 97– (2003) · Zbl 1072.05537
[14] Clark, Upper bounds for the domination number of a graph, Congr Numer 132 pp 99– (1998) · Zbl 0951.05077
[15] Clark, An inequality related to Vizing’s conjecture, Electron J Combin 7 (2000) · Zbl 0947.05056
[16] Domke, Graph Theory, Combinatorics, and Applications pp 371– (1991)
[17] Dorbec, On the upper total domination number of Cartesian products of graphs, J Comb Optim 16 (1) pp 68– (2008) · Zbl 1157.05042 · doi:10.1007/s10878-007-9099-8
[18] El-Zahar, Domination number of products of graphs, Ars Combin 31 pp 223– (1991) · Zbl 0746.05067
[19] Faudree, The domination number for the product of graphs, Congr Numer 79 pp 29– (1990) · Zbl 0862.05060
[20] Fisher, Domination, fractional domination, 2-packing, and graph products, SIAM J Discrete Math 7 (3) pp 493– (1994) · Zbl 0812.05030 · doi:10.1137/S0895480191217806
[21] Fisher, Fractional domination of strong direct products, Discrete Appl Math 50 (1) pp 89– (1994) · Zbl 0796.05055 · doi:10.1016/0166-218X(94)90165-1
[22] Hammer, Vertices belonging to all or to no maximum stable sets of a graph, SIAM J Algebraic Discrete Meth 3 (4) pp 511– (1982) · Zbl 0496.90056 · doi:10.1137/0603052
[23] Hartnell, Domination in graphs pp 163– (1998)
[24] Hartnell, On Vizing’s conjecture, Congr Numer 82 pp 87– (1991)
[25] Hartnell, Vizing’s conjecture and the one-half argument, Discuss Math Graph Theory 15 (2) pp 205– (1995) · Zbl 0845.05074 · doi:10.7151/dmgt.1018
[26] Hartnell, Lower bounds for dominating Cartesian products, J Combin Math Combin Comput 31 pp 219– (1999) · Zbl 0938.05048
[27] Hartnell, Improving some bounds for dominating Cartesian products, Discuss Math Graph Theory 23 (2) pp 261– (2003) · Zbl 1055.05115 · doi:10.7151/dmgt.1201
[28] Haynes, Paired-domination and the paired-domatic number, Congr Numer 109 pp 65– (1995) · Zbl 0904.05052
[29] Haynes, Paired-domination in graphs, Networks 32 (3) pp 199– (1998) · Zbl 0997.05074 · doi:10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
[30] Haynes, Fundamentals of Domination in Graphs (1998) · Zbl 0890.05002
[31] Henning, On the total domination number of Cartesian products of graphs, Graphs Combin 21 (1) pp 63– (2005) · Zbl 1062.05109 · doi:10.1007/s00373-004-0586-8
[32] Ho, A note on the total domination number, Util Math 77 pp 97– (2008) · Zbl 1161.05056
[33] Hou, On the k-domination number of Cartesian products of graphs, Discrete Math 309 pp 3413– (2009) · Zbl 1189.05132 · doi:10.1016/j.disc.2008.07.030
[34] Jacobson, On the domination of the products of graphs. II. Trees, J Graph Theory 10 (1) pp 97– (1986) · Zbl 0584.05053 · doi:10.1002/jgt.3190100112
[35] Khamis, Equality in Vizing’s conjecture fixing one factor of the Cartesian product, Ars Combin 96 pp 375– (2010) · Zbl 1249.05287
[36] Li, On the total k-domination number of Cartesian products of graphs, J Comb Optim 18 (2) pp 173– (2009) · Zbl 1193.05128 · doi:10.1007/s10878-008-9144-2
[37] Meir, Relations between packing and covering numbers of a tree, Pacific J Math 61 (1) pp 225– (1975) · Zbl 0315.05102 · doi:10.2140/pjm.1975.61.225
[38] Mynhardt, Vertices contained in every minimum dominating set of a tree, J Graph Theory 31 (3) pp 163– (1999) · Zbl 0931.05063 · doi:10.1002/(SICI)1097-0118(199907)31:3<163::AID-JGT2>3.0.CO;2-T
[39] Nowakowski, Associative graph products and their independence, domination and coloring numbers, Discuss Math Graph Theory 16 (1) pp 53– (1996) · Zbl 0865.05071 · doi:10.7151/dmgt.1023
[40] S. Suen J. Tarr An improved inequality related to Vizing’s conjecture 2010
[41] Sumner, Domination in Graphs pp 439– (1998)
[42] Sun, A result on Vizing’s conjecture, Discrete Math 275 (1-3) pp 363– (2004) · Zbl 1030.05087 · doi:10.1016/j.disc.2003.09.003
[43] Vizing, The cartesian product of graphs, Vyčisl Sistemy No. 9 pp 30– (1963)
[44] Vizing, Some unsolved problems in graph theory, Uspehi Mat Nauk 23 (6(144)) pp 117– (1968) · Zbl 0192.60502
[45] Y. Wu An improvement on Vizing’s conjecture 2009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.