# zbMATH — the first resource for mathematics

An inequality related to Vizing’s conjecture. (English) Zbl 0947.05056
Electron. J. Comb. 7, No. 1, Notes N4, 3 p. (2000); printed version J. Comb. 7, No. 2 (2000).
From the authors’ abstract and the text, with minor changes: Let $$\gamma(G)$$ denote the domination number of a graph $$G$$. For a pair of graphs $$G_1$$ and $$G_2$$ the Cartesian product $$G_1\square G_2$$ is the graph with vertex set $$V(G_1)\times V(G_2)$$, and where two vertices are adjacent if and only if they are equal in one coordinate and adjacent in the other. In 1963, V. G. Vizing [The Cartesian product of graphs (Russian). Vychsl. Sist. 9, 30-43 (1963; Zbl 0194.25203)] conjectured that, for any graphs $$G_1$$ and $$G_2$$, $$\gamma(G_1) \gamma(G_2)\leq \gamma(G_1\square G_2)$$. (…) We shall show in this note that $$\gamma(G_1) \gamma(G_2)\leq 2\gamma(G_1\square G_2)$$.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C35 Extremal problems in graph theory
##### Keywords:
Vizing’s conjecture; domination number
Full Text: