What is the difference between the domination and independent domination numbers of a cubic graph? (Q804588)

From MaRDI portal
Revision as of 08:47, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
What is the difference between the domination and independent domination numbers of a cubic graph?
scientific article

    Statements

    What is the difference between the domination and independent domination numbers of a cubic graph? (English)
    0 references
    0 references
    0 references
    1991
    0 references
    A dominating set in a graph G is a subset D of the vertex set V(G) of G such that for each \(x\in V(G)-D\) there exists a vertex \(y\in D\) adjacent to x. A subset of V(G) is independent, if no two of its vertices are adjacent in G. The domination number \(\alpha\) (G) (or the independent domination number \(\alpha '(G))\) of G is the minimum number of vertices of a dominating (or independent dominating) set in G. The authors present an infinite class of cubic (i.e. regular of degree 3) graphs with the connectivity 2 in which the difference \(\alpha '(G)-\alpha (G)\) is unbounded. They express a conjecture that for cubic graphs with the connectivity 3 this difference is at most 1.
    0 references
    dominating set
    0 references
    domination number
    0 references
    independent domination number
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers