Disproof of a conjecture in the domination theory (Q1343234): Difference between revisions

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating, if for each vertex \(x\in V(G)- S\) there exists a vertex \(y\in S\) adjacent to \(x\). 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 a set which is simultaneously dominating and independent in \(G\) is the independent domination number \(\alpha'(G)\) of \(G\). The authors disprove a conjecture by \textit{C. Barefoot}, \textit{F. Harary} and \textit{K. F. Jones} [Graphs Comb. 7, No. 2, 205-208 (1991; Zbl 0728.05033)] that the difference \(\alpha'(G)- \alpha(G)\) for cubic graphs with connectivity three does not exceed 1. They prove that for any \(c\in \{0,1,2,3\}\) and any integer \(k\geq 0\) there exist infinitely many cubic graphs \(G\) with connectivity \(c\) for which \(\alpha'(G)- \alpha(G)= k\). They express a conjecture that an analogous assertion holds also for regular graphs of degree greater than three.