On matching and total domination in graphs

Michael A. Henning, Liying Kang, Erfang Shan, Anders Yeo

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)

Abstract

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. 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. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k ≥ 3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.

Original languageEnglish
Pages (from-to)2313-2318
Number of pages6
JournalDiscrete Mathematics
Volume308
Issue number11
DOIs
Publication statusPublished - 6 Jun 2008
Externally publishedYes

Keywords

  • Claw-free graph
  • Cubic graph
  • Matching number
  • Total domination number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this