Some results on matching and total domination in graphs

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

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

3 Citations (Scopus)


Let G be a graph. A set S of vertices of G is called a total dominating set of G if every vertex of G is adjacent to at least one vertex in S. The total domination number γt(G) and the matching number α'(G) of G are the cardinalities of the minimum total dominating set and the maximum matching of G, respectively. In this paper, we introduce an upper bound of the difference between γt(G) and α'(G). We also characterize every tree T with γt(T) ≤ α'(T), and give a family of graphs with γt(G) ≤ α'(G).

Original languageEnglish
Pages (from-to)241-252
Number of pages12
JournalApplicable Analysis and Discrete Mathematics
Issue number2
Publication statusPublished - Oct 2010

Scopus Subject Areas

  • Analysis
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

User-Defined Keywords

  • Induced matching number
  • Matching number
  • Total domination number


Dive into the research topics of 'Some results on matching and total domination in graphs'. Together they form a unique fingerprint.

Cite this