## Paired-domination in claw-free cubic graphs.(English)Zbl 1054.05074

Summary: A set $$S$$ of vertices in a graph $$G$$ is a paired-dominating set of $$G$$ if every vertex of $$G$$ is adjacent to some vertex in $$S$$ and if the subgraph induced by $$S$$ contains a perfect matching. The minimum cardinality of a paired-dominating set of $$G$$ is the paired-domination number of $$G$$, denoted by $$\gamma_{\text{pr}}(G)$$. If $$G$$ does not contain a graph $$F$$ as an induced subgraph, then $$G$$ is said to be $$F$$-free. In particular if $$F=K_{1,3}$$ or $$K_4-e$$, then we say that $$G$$ is claw-free or diamond-free, respectively. Let $$G$$ be a connected cubic graph of order $$n$$. We show that (i) if $$G$$ is $$(K_{1,3},K_4-e,C_4)$$-free, then $$\gamma_{\text{pr}}(G)\leq 3n/8$$; (ii) if $$G$$ is claw-free and diamond-free, then $$\gamma_{\text{pr}}(G)\leq 2 n/5$$; (iii) if $$G$$ is claw-free, then $$\gamma_{\text{pr}}(G)\leq n/2$$. In all three cases, the extremal graphs are characterized.

### MSC:

 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C35 Extremal problems in graph theory

### Keywords:

Bounds; Claw-Free cubic graphs; Paired-domination
Full Text: