×

zbMATH — the first resource for mathematics

A \(\frac{3}{4}\)-approximation of Vizing’s conjecture for claw-free graphs. (English) Zbl 1443.05138
Summary: Vizing’s conjecture [V. G. Vizing, Vychisl. Sistemy, Novosibirsk 9, 30–43 (1963; Zbl 0194.25203)] asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. We prove that for any claw-free graph \(G\) and an arbitrary graph \(H\), the inequality \(\gamma (G \square H) \geq \frac{3}{4} \gamma (G) \gamma (H)\) always holds.
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, R.; Szabó, T., Vizing’s conjecture for chordal graphs, Discrete Math., 309, 1766-1768 (2009) · Zbl 1211.05098
[2] Allan, R. B.; Laskar, R., On domination and independent domination numbers of a graph, Discrete Math., 23, 73-76 (1978) · Zbl 0416.05064
[3] Anderson, S. E.; Nagpal, S.; Wash, K., Domination in the hierarchical product and Vizing’s conjecture, Discrete Math., 341, 20-24 (2018) · Zbl 1372.05155
[4] Barcalkin, A. M.; German, L. F., The external stability number of the Cartesian product of graphs, Bul. Akad. Stiinte RSS Mold., 94, 5-8 (1979)
[5] Brešar, B.; Dorbec, P.; Goddard, W.; Hartnell, B. L.; Henning, M. A.; Klavžar, S.; Rall, D. F., Vizing’s conjecture: a survey and recent results, J. Graph Theory, 69, 46-76 (2012) · Zbl 1234.05173
[6] Brešar, B., Vizing’s conjecture for graphs with domination number 3—a new proof, Electron. J. Combin., 22 (2015), Paper 3.38, 8 pp · Zbl 1323.05099
[7] Brešar, B., Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs, Discrete Math., 340, 2398-2401 (2017) · Zbl 1367.05155
[8] Brešar, B.; Rall, D. F., Fair reception and Vizing’s conjecture, J. Graph Theory, 61, 45-54 (2009) · Zbl 1179.05080
[9] Clark, W. E.; Suen, S., An inequality related to Vizing’s conjecture, Electron. J. Combin., 7 (2000), #N4, 3 pp · Zbl 0947.05056
[10] González Yero, I., Partial product of graphs and Vizing’s conjecture, Ars Math. Contemp., 9, 19-25 (2015) · Zbl 1332.05106
[11] Hartnell, B. L.; Rall, D. F., Vizing’s conjecture and the one-half argument, Discuss. Math. Graph Theory, 15, 205-216 (1995) · Zbl 0845.05074
[12] Hartnell, B.; Rall, D. F., Domination in Cartesian products: Vizing’s conjecture, (Domination in Graphs. Domination in Graphs, Monogr. Textbooks Pure Appl. Math., vol. 209 (1998), Dekker: Dekker New York), 163-189 · Zbl 0890.05035
[13] Krop, E., Vizing’s conjecture: a two-thirds bound for claw-free graphs, Discrete Appl. Math., 230, 162-165 (2017) · Zbl 1368.05113
[14] Milanič, M., A note on domination and independence-domination numbers of graphs, Ars Math. Contemp., 6, 89-97 (2013) · Zbl 1301.05253
[15] Ore, O., Theory of Graphs, 206-212 (1962), American Mathematical Society: American Mathematical Society Providence (RI)
[16] Suen, S.; Tarr, J., An improved inequality related to Vizing’s conjecture, Electron. J. Combin., 19 (2012), #P8, 4 pp · Zbl 1243.05190
[17] Sun, L., A result on Vizing’s conjecture, Discrete Math., 275, 363-366 (2004) · Zbl 1030.05087
[18] Vizing, V. G., The cartesian product of graphs, Vychisl. Sistemy, 9, 30-43 (1963)
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.