Vizing's conjecture for graphs with domination number 3 -- a new proof (Q888596)

From MaRDI portal
Revision as of 23:36, 10 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Vizing's conjecture for graphs with domination number 3 -- a new proof
scientific article

    Statements

    Vizing's conjecture for graphs with domination number 3 -- a new proof (English)
    0 references
    0 references
    2 November 2015
    0 references
    Summary: Vizing's conjecture [\textit{V. G. Vizing}, Russ. Math. Surv. 23, No. 6, 125--141 (1968); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968; Zbl 0192.60502)] asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this note we use a new, transparent approach to prove Vizing's conjecture for graphs with domination number 3; that is, we prove that for any graph \(G\) with \(\gamma(G)=3\) and an arbitrary graph \(H\), \(\gamma(G\square H) \geq 3\gamma(H)\).
    0 references
    Cartesian product
    0 references
    domination
    0 references
    Vizing's conjecture
    0 references

    Identifiers