×

zbMATH — the first resource for mathematics

Vizing’s conjecture for graphs with domination number 3 – a new proof. (English) Zbl 1323.05099
Summary: Vizing’s conjecture [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)\).

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: Link