Paired-domination in claw-free graphs (Q2637727): Difference between revisions

A paired-dominating set of a graph \(G\) is a dominating set \(S\) of vertices such that there exists a perfect matching in the subgraph induced by \(S\). The paired-domination number, denoted by \(\gamma_{pr}(G)\), is the minimum cardinality of a paired-dominating set in \(G\). The authors show that \(\gamma_{pr}(G) \leq (3n - 1)/5\) if \(G\) is a connected claw-free (i.e., \(K_{1,3}\)-free) graph of order \(n\) with minimum degree at least three. The bound is sharp. The authors also propose the following conjecture. If \(G\) is a connected claw-free graph of order \(n\) with minimum degree at least three, then \(\gamma_{pr}(G) \leq 4n/7\). This is a weaker form of a conjecture proposed by \textit{W. Goddard} and \textit{M. A. Henning} [Graphs Comb. 25, No. 5, 675--692 (2009; Zbl 1203.05117)] that asserts the same consequence for any connected graph \(G\), except the Petersen graph, of order \(n\) with minimum degree at least three.