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
    0 references
    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
    0 references
    Vizing's conjecture
    0 references
    domination number
    0 references