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 G, denoted by , is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m≥18 with minimum degree at least 2, then and we characterize the (infinite family of) graphs that achieve equality in this bound.