zbMATH — the first resource for mathematics

An improved inequality related to Vizing’s conjecture. (English) Zbl 1243.05190
Summary: V. G. Vizing conjectured in 1963 [Vychisl. Sistemy, Novosibirsk 9, 30–43 (1963; Zbl 0194.25203)] that \(\gamma(G \square H) \geq \gamma(G)\gamma(H)\) for any graphs \(G\) and \(H\). A graph \(G\) is said to satisfy Vizing’s conjecture if the conjectured inequality holds for \(G\) and any graph \(H\). Vizing’s conjecture has been proved for \(\gamma(G) \leq 3\), and it is known to hold for other classes of graphs.
W. E. Clark and S. Suen in 2000 [Electron. J. Comb. 7, No. 1, Notes N4, 3 p. (2000); printed version J. Comb. 7, No. 2 (2000; Zbl 0947.05056)] showed that \(\gamma(G \square H) \geq \frac{1}{2}\gamma(G)\gamma(H)\) for any graphs \(G\) and \(H\). We give a slight improvement of this inequality by tightening their arguments.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
Full Text: EMIS