Upper total domination versus upper paired-domination

Paul Dorbec, Michael A. Henning, John McCoy

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


Let G be a graph with no isolated vertices. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S, while a paired-dominating set of G is a dominating set of vertices whose induced subgraph has a perfect matching. The maximum cardinality of a minimal total dominating set and a minimal paired-dominating set of G is the upper total domination number and upper paired-domination number of G, respectively, denoted by Γt(G) and Γpr, (G). In this paper, we investigate the relationship between the upper total domination and upper paired-domination numbers of a graph. We show that for every graph G with no isolated vertex Γt(G) ≥ 1/2(Γpr(G) + 2), and we characterize the trees achieving this bound. For each positive integer k, we observe that there exist connected graphs G and H such that Γpr(G) - Γt(G) ≥ k and Γt(H) - Γpr(H) ≥ k. However for the family of trees T on at least two vertices, we show that Gamma;t(T) ≤ Γpr(T).

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalQuaestiones Mathematicae
Issue number1
Publication statusPublished - Mar 2007
Externally publishedYes


  • Bounds
  • Upper paired-domination
  • Upper total domination

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Upper total domination versus upper paired-domination'. Together they form a unique fingerprint.

Cite this