Upper bounds on the paired-domination number

Xue gang Chen*, Wai Chee SHIU, Wai Hong Chan

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

11 Citations (Scopus)


A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by γp r (G). In this work, we present several upper bounds on the paired-domination number in terms of the maximum degree, minimum degree, girth and order.

Original languageEnglish
Pages (from-to)1194-1198
Number of pages5
JournalApplied Mathematics Letters
Issue number11
Publication statusPublished - Nov 2008

Scopus Subject Areas

  • Applied Mathematics

User-Defined Keywords

  • Girth
  • Maximum degree
  • Minimum degree
  • Paired-domination number


Dive into the research topics of 'Upper bounds on the paired-domination number'. Together they form a unique fingerprint.

Cite this