A vertex set S of a graph G is called an independent dominating set if S is an independent set and each vertex in V(G)\S is adjacent to a vertex in S. The independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. This paper first proves that if G is a connected \(K_{1,3}\)-free cubic graph, then \(i(G)\leq \frac{1}{3}|V(G)|\). Meanwhile, \(i(G)=\frac{1}{3}|V(G)|\) if and only if \(G\in \mathcal{H}\), where \(\mathcal{H}\) is an infinite cubic family with each graph being a \(C_6^+\)-necklace. Then, it is shown that if G is a \(\{K_{1,3}, K_4^-, C_6^+\}\)-free cubic graph with no \(C_3\Box K_2\)-component, then \(i(G)\leq \frac{5}{18}|V(G)|\). This result is tight.

Articles

Independent Domination in Claw-Free Cubic Graphs