The independent domination number of a cubic 3-connected graph can be much larger than its domination number (Q687719)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The independent domination number of a cubic 3-connected graph can be much larger than its domination number |
scientific article |
Statements
The independent domination number of a cubic 3-connected graph can be much larger than its domination number (English)
0 references
28 October 1993
0 references
A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is dominating, if for each vertex \(x \in V(G)-D\) there exists \(y \in D\) adjacent to \(x\). It is independent, if no two of its vertices are adjacent in \(G\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\alpha(G)\) of \(G\). The minimum number of vertices of an independent dominating set in \(G\) is the independent domination number \(\alpha'(G)\) of \(G\). An infinite family \(\{G_ n\}\) of cubic 3-connected graphs on 130\(n\) vertices with \(\alpha'(G)-\alpha(G) \geq n\) is constructed. This proves that the difference \(\alpha'(G)-\alpha(G)\) may be arbitrarily large and disproves a conjecture of C. Barefoot, F. Harary and K. F. Jones.
0 references
dominating set
0 references
domination number
0 references
independent dominating set
0 references
independent domination number
0 references