Independent Domination in Claw-Free Cubic Graphs

Source abstract

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.