Trees with paired-domination number twice their domination number

Michael A. Henning, Preben Dahl Vestergaard

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


We continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199-206). A paired-dominating set of a graph G with no isolated vertex is a domi-nating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G is the minimum cardinality of a paired-dominating set of G. For k ≥ 2, a k-packing in G is a set S of vertices of G that are pairwise at distance greater than k apart. The fc-packing number of G is the maximum cardinality of a k-packing in G. Haynes and Slater observed that the paired-domination number is bounded above by twice the domination number. We give a constructive characterization of the trees attaining this bound that uses labelings of the vertices. The key to our characterization is the observation that the trees with paired-domination number twice their domination number are precisely the trees with 2-packing number equal to their 3-packing number.

Original languageEnglish
Pages (from-to)187-197
Number of pages11
JournalUtilitas Mathematica
Publication statusPublished - Nov 2007
Externally publishedYes


  • Domination
  • Packing number
  • Paired-domination

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'Trees with paired-domination number twice their domination number'. Together they form a unique fingerprint.

Cite this