Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set

Teresa W. Haynes
Michael A. Henning

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 \(\operatorname{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 \geq 5\) satisfies \(\operatorname{ti}(T) \leq \frac{1}{5}n\). We prove that if \(G\) is a bipartite graph of order \(n\) with minimum degree \(\delta(G) \geq 3\), then \(\operatorname{ti}(G) \leq \frac{1}{4}n\), and if \(G\) is a cubic graph of order \(n\), then \(\operatorname{ti}(G) \leq \frac{1}{3}n\). We conjecture that \(\operatorname{ti}(G) \leq \frac{1}{6}n\) for all graphs \(G\) of order \(n\) with \(\delta(G) \geq 3\), and show that there exist connected graphs \(G\) of sufficiently large order \(n\) with \(\delta(G) \geq 3\) such that \(\operatorname{ti}(T) \geq (\frac{1}{6} - \varepsilon) n\) for any given \(\varepsilon \gt 0\).

Keywords: total domination, independent domination, vertex partitions.

Mathematics Subject Classification: 05C69.

Full text (pdf)