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.


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