TY  - JOUR
ID  - Haynes2022
LB  - Haynes2022
AU  - Haynes, Teresa W.
AU  - Henning, Michael A.
TI  - Nordhaus-Gaddum bounds for upper total domination
ST  - Nordhaus-Gaddum bounds for upper total domination
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2022
VL  - 42
IS  - 4
SP  - 573
EP  - 582
DO  - https://doi.org/10.7494/OpMath.2022.42.4.573
UR  - https://doi.org/10.7494/OpMath.2022.42.4.573
AB  - 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.
KW  - upper total domination
KW  - Nordhaus-Gaddum bounds
SN  - 1232-9274
ER  -