On the existence of k-partite or K^p-free 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). The graph G is 3_t-critical if ^γt(G)=3 and ^γt(G+e)=2 for every edge e in the complement of G. We show that no bipartite graph is 3_t-critical. The tripartite 3 _t-critical graphs are characterized. For every k<3, we prove that there are only a finite number of 3_t-critical k-partite graphs. We show that the 5-cycle is the only 3_t-critical ^K3-free graph and that there are only a finite number of 3_t-critical ^K4-free graphs.