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

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.