# 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.)
##### Keywords:
Cartesian product; domination; Vizing’s conjecture
Full Text: