Abstract
A graph G whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. There exist infinite families of graphs that are not TI-graphs. We define the TI-augmentation number ti(G) of a graph G to be the minimum number of edges that must be added to G to ensure that the resulting graph is a TI-graph. We show that every tree T of order n> 5 satisfies ti(T) < 1/5n. We prove that if G is a bipartite graph of order n with minimum degree 8(G) > 3, then ti(G) < 1/4n, and if G is a cubic graph of order n, then ti(G) < 13n. We conjecture that ti(G) < 16n for all graphs G of order n with 8(G) > 3, and show that there exist connected graphs G of sufficiently large order n with 8(G) > 3 such that ti(T) > ( 16-epsilon)n for any given epsilon > 0.