Paired-Domination in Claw-Free Cubic Graphs.

A setSof vertices in a graphGis a paired-dominating set ofGif every vertex ofGis adjacent to some vertex inSand if the subgraph induced byScontains a perfect matching. The minimum cardinality of a paired-dominating set ofGis the paired-domination number ofG, denoted by ?pr(G). IfGdoes not contain a graphFas an induced subgraph, thenGis said to beF-free. In particular ifF=K1,3 orK4-e, then we say thatGis claw-free or diamond-free, respectively. LetGbe a connected cubic graph of ordern. We show that (i) ifGis (K1,3,K4-e,C4)-free, then ?pr(G)=3n/8; (ii) ifGis claw-free and diamond-free, then ?pr(G)=2n/5; (iii) ifGis claw-free, then ?pr(G)=n/2. In all three cases, the extremal graphs are characterized. [ABSTRACT FROM AUTHOR]