## 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 S of vertices in G is a total dominating set 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. We prove that if all vertices of G belong to a triangle, then the total domination number of G is bounded above by its matching number. We in fact prove a slightly stronger result and as a consequence of this stronger result, we prove a Graffiti conjecture that relates the total domination and matching numbers in a graph.

Original language | English |
---|---|

Pages (from-to) | 174-181 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 313 |

Issue number | 2 |

DOIs | |

Publication status | Published - 28 Jan 2013 |

## Keywords

- Matching number
- Total domination number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics