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 G is the minimum cardinality of a paired-dominating set in G. 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 Erdos 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≥2, let G be a graph with paired-domination number 2k, order n≥2k, and size m. As a consequence of the Erdos-Rényi result it follows that if k=2, then m≤n2-k(n-2)+1. For k≥3, we show that m≤n2-k(n-2) and we characterize the graphs that achieve equality in this bound.