What is the difference between the domination and independent domination numbers of a cubic graph? (Q804588)
From MaRDI portal
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
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