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\).

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI Link