An inequality related to Vizing's conjecture (Q1568837)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An inequality related to Vizing's conjecture |
scientific article |
Statements
An inequality related to Vizing's conjecture (English)
0 references
23 July 2000
0 references
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, \textit{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)\). (\dots) We shall show in this note that \(\gamma(G_1) \gamma(G_2)\leq 2\gamma(G_1\square G_2)\).
0 references
Vizing's conjecture
0 references
domination number
0 references