NORDHAUS–GADDUM BOUNDS FOR UPPER TOTAL DOMINATION

A set S of vertices in an isolate-free graph G is a total dominating set if every vertex in G is adjacent to a vertex in S. A total dominating set of G is minimal if it contains no total dominating set of G as a proper subset. The upper total domination number Γt(G) of G is the maximum cardinality of a minimal total dominating set in G. We establish Nordhaus–Gaddum bounds involving the upper total domination numbers of a graph G and its complement G. We prove that if G is a graph of order n such that both G and G are isolate-free, then Γt(G) + Γt(G) ≤ n + 2 and Γt(G)Γt(G) ≤ ¹₄(n + 2)², and these bounds are tight.