The independent domination number of a cubic 3-connected graph can be much larger than its domination number (Q687719)

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.