# 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.

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