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

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
Full Text: EMIS EuDML