An upper bound on the paired-domination number in terms of the number of edges in the graph

In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199–206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph GG, denoted by γpr(G), is the minimum cardinality of a paired-dominating set in GG. We show that if GG is a connected graph of size m≥18m≥18 with minimum degree at least 2, then γpr(G)≤4m/7 and we characterize the (infinite family of) graphs that achieve equality in this bound.