Graphs with maximum size and given paired-domination number

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 is the minimum cardinality of a paired-dominating set in GG. We determine the maximum possible number of edges in a graph with given order and given paired-domination number and we completely characterize the infinite family of graphs that achieve this maximum possible size. Our result builds on a classic result in 1962 due to Erdős and Rényi (1962) since the case when the paired-domination is four is equivalent to determining the minimum size of a nontrivial diameter-2 graph (excluding a star) in the complement of the graphs we are considering. More precisely, for k≥2k≥2, let GG be a graph with paired-domination number 2k2k, order n≥2kn≥2k, and size mm. As a consequence of the Erdős–Rényi result it follows that if k=2k=2, then m≤n2−k(n−2)+1. For k≥3k≥3, we show that m≤n2−k(n−2) and we characterize the graphs that achieve equality in this bound.