Nordhaus-Gaddum bounds for upper total domination

Abstract

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 $\Gamma_{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 $\overline{G}$. We prove that if $G$ is a graph of order n such that both $G$ and $\overline{G}$ are isolate-free, then $\Gamma_t(G) + \Gamma_t(\overline{G}) \leq n + 2$ and $\Gamma_t(G)\Gamma_t(\overline{G}) \leq \frac{1}{4}(n+2)^2$, and these bounds are tight.