The Paired Domination Problem Of Claw-free Graphs

Let G＝(V, E) be a simple undirected graph without isolated vertices. A set S (?) V is a dominating set of G if every vertex in V\S is adjacent to at least one vertex in S. A set S (?) V is a paired-dominating set of G if S is a dominating set of G and the induced subgraph G[S] at least has a perfect matching. The paired-domination number of G, denoted by γpr(G), is defined as min{|S‖S is a paired-dominating set of G}. The paired-domination problem is to determine the paired-domination number of a given graph. This problem was proposed by Haynes and Slater in1998, and they proved that it is NP-hard for general graphs. In2009, Goddard and Henning proposed a conjecture that if G≠P is a connected graph with minimum degree at least3, then γpr(G)≤4n/7, where P is the Petersen graph. In this paper, we consider the paired-domination problem around this conjecture. We prove that if G is a connected claw-free graph of order n, then γpr(G)≤4n/7, and we also give an extremal graph that achieves the upper bound. This result implies that the conjecture is true for the connected claw-free graph and improves the former’s results on the upper bounds of paired-domination numbers.