## Abstract

A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The total domination number, γ_{t} (G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [J. Combin. Math. Combin. Comput.58 (2006), 189–193] showed that if T is a nontrivial tree of order n, with ℓ leaves, then γ_{t} (T) ≥ (n − ℓ + 2)/2. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γ_{t} (T) = ⌈(n−ℓ+2)/2⌉. We then generalize this result to connected graphs and show that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and ℓ leaves, then γ_{t} (G) ≥ ⌈(n − ℓ + 2)/2⌉ − k. We also characterize the graphs G achieving equality for this new bound.

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

Pages (from-to) | 35-48 |

Number of pages | 14 |

Journal | Quaestiones Mathematicae |

Volume | 46 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2023 |

## Keywords

- Total domination
- cycles
- lower bounds

## ASJC Scopus subject areas

- Mathematics (miscellaneous)