Graphs with maximum size and given paired-domination number

Michael A. Henning, John McCoy, Justin Southey

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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 languageEnglish
Pages (from-to)72-82
Number of pages11
JournalDiscrete Applied Mathematics
Publication statusPublished - 19 Jun 2014


  • Maximum size
  • Paired-domination
  • Vizing bounds

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Graphs with maximum size and given paired-domination number'. Together they form a unique fingerprint.

Cite this