An inequality related to Vizing's conjecture (Q1568837)

From MaRDI portal
Revision as of 02:16, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
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