## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 72-82 |

Number of pages | 11 |

Journal | Discrete Applied Mathematics |

Volume | 170 |

DOIs | |

Publication status | Published - 19 Jun 2014 |

## Keywords

- Maximum size
- Paired-domination
- Vizing bounds

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics