An inequality related to Vizing's conjecture (Q1568837)

From MaRDI portal
Revision as of 04:56, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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