×

zbMATH — the first resource for mathematics

An improved bound in Vizing’s conjecture. (English) Zbl 1431.05118
Summary: A well-known conjecture of V. G. Vizing [Vychisl. Sist., Novosibirsk 9, 30–43 (1963; Zbl 0194.25203)] is that \(\gamma (G \Box H) \ge \gamma(G) \gamma(H)\) for any pair of graphs \(G, H\), where \(\gamma\) is the domination number and \(G \Box H\) is the Cartesian product of \(G\) and \(H\). S. Suen and J. Tarr [Electron. J. Comb. 19, No. 1, Research Paper P8, 4 p. (2012; Zbl 1243.05190)] improving a result of S. Suen and J. Tarr [Electron. J. Comb. 19, No. 1, Research Paper P8, 4 p. (2012; Zbl 1243.05190)], showed \(\gamma (G \Box H) \ge \frac{1}{2}\gamma (G)\gamma (H) + \frac{1}{2}\min(\gamma (G), \gamma (H))\). We further improve their result by showing \(\gamma (G \Box H) \ge \frac{1}{2}\gamma(G) \gamma(H) + \frac{1}{2}\max(\gamma(G), \gamma(H))\).

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 arXiv
References:
[1] Asplund, J.; Davila, R.; Krop, E., A Vizing-type result for semi-total domination, Discret. Appl. Math., 258, 8-12 (2019) · Zbl 1407.05172
[2] Barcalkin, AM; German, LF, The external stability number of the Cartesian product of graphs, Bul. Akad. Stiinte RSS Moldoven, 94, 5-8 (1979)
[3] Brešar, B., Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs, Discret. Math., 340, 2398-2401 (2017) · Zbl 1367.05155
[4] Brešar, B.; Dorbec, P.; Goddard, W.; Hartnell, BL; Henning, MA; Klavžar, S.; Rall, DF, Vizing’s conjecture: a survey and recent results, J. Graph Theory, 69, 46-76 (2012) · Zbl 1234.05173
[5] Clark, WE; Suen, S., An inequality related to Vizing’s conjecture, Electron. J. Comb., 7, note 4 (2000) · Zbl 0947.05056
[6] Hartnell, B.; Rall, DF; Haynes (ed.); etal., Domination in Cartesian products: Vizing’s conjecture, 163-189 (1998), New York · Zbl 0890.05035
[7] Suen, S.; Tarr, J., An improved inequality related to Vizing’s conjecture, Electron. J. Comb., 19, 1 (2012) · Zbl 1243.05190
[8] Vizing, VG, The Cartesian product of graphs, Vyčisl. 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.