Vizing's conjecture for graphs with domination number 3 -- a new proof (Q888596): Difference between revisions

Summary: Vizing's conjecture [\textit{V. G. Vizing}, Russ. Math. Surv. 23, No. 6, 125--141 (1968); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968; Zbl 0192.60502)] 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 note we use a new, transparent approach to prove Vizing's conjecture for graphs with domination number 3; that is, we prove that for any graph \(G\) with \(\gamma(G)=3\) and an arbitrary graph \(H\), \(\gamma(G\square H) \geq 3\gamma(H)\).