On independent domination number of regular graphs (Q1301709): Difference between revisions

A subset \(S\) of the vertex set of a graph \(G\) is called independent, if no two of its vertices are adjacent in \(G\). An independent set in \(G\) is maximal, if it is not a proper subset of another independent set of \(G\). The minimum number of vertices of a maximal independent set is the independent domination number \(i(G)\) of \(G\). A conjecture of J. Haviland says that a regular graph \(G\) of degree \(\delta\leq n/2\) (where \(n\) is the number of vertices of \(G\)) has \(i(G)\leq\lceil 2n/3\rceil \delta/2\). In the paper this conjecture is disproved by giving two counterexamples. Then for a connected cubic graph \(G\) with \(n>3\) vertices the inequality \(i(G)\leq 2n/5\) is proved.