Augmenting Trees to have Two Disjoint Total Dominating Sets

Abstract

A tot.al dominating se t of a graph G = (V, E) is a set S o f vertices such that every vertex is adjacent to a vertex in S. Define td (G) as the minimum number of edges that must be added to G to ensure a partition of V into two total dominating sets of the resulting graph . We show that if G is a tree, l(G)/2≤ td(G) ≤l(G) /2 + I, where l(G) is the number or leaves of G.