Graphs with large total domination number
Michael A. Henning · Journal of Graph Theory · 2000
Let G = (V,E) be a graph. A set S ⊆ V is 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 ∈ {C3, C5, C6, C10}. 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. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 21–45, 2000