## Abstract

Let G= (V,E) be a graph. A set S⊆ Vis a total dominating set if every vertex of V is adjacent to some vertex in S. The total domination number of G, denoted by _{γt}(G), is the minimum cardinality of a total dominating set of G. We establish a property of minimum total dominating sets in graphs. If G is a connected graph of order n≥3, then (see [3]) _{γt},(G)≤2n/3. We show that if G is a connected graph of order n with minimum degree at least 2, then either _{γt}(G) ≤ 4n/7 or Gε {C_{3}, C_{5}, C_{6}, C_{10}}. A characterization of those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G) ≥ 2 and _{γt}(G) ≥ 4n/7 is obtained. We establish that if G is a connected graph of size q with minimum degree at least 2, then _{γt}(G) ≤ (q+2)/2. Connected graphs G of size q with minimum degree at least 2 satisfying _{γt}(G) ≥ q/2 are characterized.

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

Pages (from-to) | 21-45 |

Number of pages | 25 |

Journal | Journal of Graph Theory |

Volume | 35 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2000 |

Externally published | Yes |

## Keywords

- Bounds
- Minimum degree two
- Total domination

## ASJC Scopus subject areas

- Geometry and Topology