## 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 language | English |
---|---|

Pages (from-to) | 2313-2318 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 11 |

DOIs | |

Publication status | Published - 6 Jun 2008 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics