AUGMENTING GRAPHS TO PARTITION THEIR VERTICES INTO A TOTAL DOMINATING SET AND AN INDEPENDENT DOMINATING SET

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)(Formula presented). We prove that if G is a bipartite graph of order n with minimum degree δ(G) ≥ 3, then ti(G)(Formula presented), and if G is a cubic graph of order n, then ti(G)(Formula presented). We conjecture that ti(G)(Formula presented) for all graphs G of order n with δ(G) ≥ 3, and show that there exist connected graphs G of sufficiently large order n with δ(G) ≥ 3 such that ti(T)(Formula presented) for any given ε > 0.