Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

AbstractA total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most (n-2n)/4+O(logn) edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible