Graphs with large total domination number

Let G=(V, E) be a graph. A set SC Vis a total dominating set if every verte x of Vis adjacent to some vertex in S. The total domination number of G, de noted by gamma(t)(G), is the minimum cardinality of a total dominating set of G. We establish a property of minimum total dominating sets in graphs. I f G is a connected graph of order n greater than or equal to 3, then (see [ 3]) gamma(t)(G) less than or equal to 2n/3. We show that ii G is a connecte d graph of order n with minimum degree at least 2, then either gamma(t)(G) less than or equal to 4n/7 or G epsilon {C-3, C-5, C-6, C-10}. A characteri zation of those graphs of order n which are edge-minimal with respect to sa tisfying G connected, S(G) greater than or equal to 2 and gamma(t)(G) great er than or equal to 4n/7 is obtained. We establish that if G is a connected graph of size q with minimum degree at least 2, then gamma(t)(G) less than or equal to (q+ 2)/2. Connected graphs G of size q with minimum degree at least 2 satisfying gamma(t)(G) > q/2 are characterized. (C) 2000 John Wiley & Sons, Inc.