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) ≤ 1/5n. We prove that if G is a bipartite graph of order n with minimum degree δ(G) ≥ 3, then ti(G) ≤ 1/4n, and if G is a cubic graph of order n, then ti(G) ≤ 1/3n. We conjecture that ti(G) ≤ 1/6n 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) ≥ (1/6− ε)n for any given ε > 0.

---

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)