Total domination and matching numbers in claw-free graphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

10 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. The matching number of G is the maximum cardinality of a matching of G. A set 5 of vertices in G is a, total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. If G does not contain K1,3 as an induced subgraph, then G is said to be claw-free. 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. In this paper, we use transversals in hypergraphs to characterize connected claw-free graphs with minimum degree at least three that have equal total domination and matching numbers.

Original languageEnglish
Pages (from-to)1-28
Number of pages28
JournalElectronic Journal of Combinatorics
Volume13
Issue number1 R
DOIs
Publication statusPublished - 28 Jul 2006
Externally publishedYes

Keywords

  • Claw-free
  • Matching number
  • Total domination number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Total domination and matching numbers in claw-free graphs'. Together they form a unique fingerprint.

Cite this