The independent domination number of a cubic 3-connected graph can be much larger than its domination number
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.
- What is the difference between the domination and independent domination numbers of a cubic graph?
- Disproof of a conjecture in the domination theory
- Cubic graphs with large ratio of independent domination number to domination number
- scientific article; zbMATH DE number 867653
- A counterexample to conjecture of Barefoot, Harary, and Jones
- On the independent domination number of regular graphs
- Independent domination in bipartite cubic graphs
- Independent domination in subcubic graphs
- An improved upper bound on the independent domination number in cubic graphs of girth at least six
- On independent domination in planar cubic graphs
- A counterexample to conjecture of Barefoot, Harary, and Jones
- Independent domination in subcubic graphs of girth at least six
- Cubic graphs with large ratio of independent domination number to domination number
- Independent domination in cubic graphs
- Domination versus independent domination in cubic graphs
- scientific article; zbMATH DE number 734465 (Why is no real title available?)
- A structural approach for independent domination of regular graphs
- The independent domination numbers of strong product of two cycles
- On domination in Hamiltonian cubic graphs
- A Note on Isolate Domination Number of a Cubic Graph
- Domination versus independent domination in regular graphs
- Partial domination in supercubic graphs
- What is the difference between the domination and independent domination numbers of a cubic graph?
This page was built for publication: The independent domination number of a cubic 3-connected graph can be much larger than its domination number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687719)
