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 language | English |
|---|---|
| Pages (from-to) | 1-28 |
| Number of pages | 28 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 13 |
| Issue number | 1 R |
| DOIs | |
| Publication status | Published - 28 Jul 2006 |
| Externally published | Yes |
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