# zbMATH — the first resource for mathematics

On Vizing’s conjecture. (English) Zbl 0989.05084
Summary: A dominating set $$D$$ for a graph $$G$$ is a subset of $$V(G)$$ such that any vertex in $$V(G)-D$$ has a neighbor in $$D$$, and a domination number $$\gamma(G)$$ is the size of a minimum dominating set for $$G$$. For the Cartesian product $$G\square H$$ Vizing’s conjecture [cf. V. G. Vizing, Vychisl. Sistemy, Novosibirsk 9, 30-43 (1963; Zbl 0194.25203)] states that $$\gamma(G\square H)\geq(G)\gamma(H)$$ for every pair of graphs $$G$$, $$H$$. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when $$\gamma(G)= \gamma(H)= 3$$.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
##### Keywords:
domination number; Cartesian product
Full Text: