Upper Bounds for the Paired-Domination Numbers of Graphs

A set (Ssubseteq V) is a paired-dominating set if every vertex in (V{setminus } S) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by (gamma _{pr}(G)), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree (delta (G)ge 3), then (gamma _{pr}(G)le 4n/7). In this paper, we confirm this conjecture for k-regular graphs with (kge 4).