The maximum diameter of total domination edge-critical graphs

A set S of vertices in a graph G 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 graph G is total domination edge-critical if for every edge e in the complement of G , γ t ( G + e ) < γ t ( G ) . We call such graphs γ t E C . If G is γ t E C and γ t ( G ) = k , we say that G is k t E C . For k ≥ 2 , we show that the maximum diameter of a k t E C graph is at least ⌊ 3 ( k − 1 ) / 2 ⌋ and this bound is sharp for small k ≤ 6 .