## Abstract

A set S of vertices in a graph G without isolated vertices 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 γ _{t}(G) of G. The girth of G is the length of a shortest cycle in G. Let G be a connected graph with minimum degree at least 2, order n and girth g ≥ 3. It was shown in an earlier manuscript (Henning and Yeo in Graphs Combin 24:333-348, 2008) that γ _{t}(G)≤(1/2+1/g)n, and this bound is sharp for cycles of length congruent to two modulo four.In this paper we show that γ _{t}(G)≤n/2+max(1,n/2(g+1)), and this bound is sharp.

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

Pages (from-to) | 199-214 |

Number of pages | 16 |

Journal | Graphs and Combinatorics |

Volume | 28 |

Issue number | 2 |

DOIs | |

Publication status | Published - Mar 2012 |

## Keywords

- Girth
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics