## Abstract

A set S of vertices in a graph 6 is a total dominating set of 6 if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of 6 is the total domination number Γ_{t}(G) of G. It is known [J Graph Theory 35 (2000), 21-45] that if 6 is a connected graph of order n > 10 with minimum degree at least 2, then Γ_{t}(G) = 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of An/1 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if 6 is a 2-connected graph of order n > 18, then Γ_{t}(G) = 6/7/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6-cycle, then Γ_{t}(G) = 6n/11. Both bounds are shown to be sharp.

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

Pages (from-to) | 55-79 |

Number of pages | 25 |

Journal | Journal of Graph Theory |

Volume | 60 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 2009 |

Externally published | Yes |

## Keywords

- 2-connected
- Bounds
- C-free
- Total domination
- Transversals

## ASJC Scopus subject areas

- Geometry and Topology