Graphs with large paired-domination number

Research output: Contribution to journalArticlepeer-review

44 Citations (Scopus)


In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199-206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γpr(G), is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199-206, showed that if n ≥ 6, then γpr(G) ≤ 2n/3. In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that γpr(G)≤ 2(n-1)/3 and we characterize the (infinite family of) graphs that achieve equality in this bound.

Original languageEnglish
Pages (from-to)61-78
Number of pages18
JournalJournal of Combinatorial Optimization
Issue number1
Publication statusPublished - Jan 2007
Externally publishedYes


  • Bounds
  • Minimum degree two
  • Paired-domination

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


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

Cite this