Opuscula Math. 42, no. 4 (2022), 573-582
https://doi.org/10.7494/OpMath.2022.42.4.573
Opuscula Mathematica
Nordhaus-Gaddum bounds for upper total domination
Teresa W. Haynes
Michael A. Henning
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.
Keywords: upper total domination, Nordhaus-Gaddum bounds.
Mathematics Subject Classification: 05C69.
- M. Aouchiche, P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013), 466-546. https://doi.org/10.1016/j.dam.2011.12.018
- E.J. Cockayne, R.M. Dawes, S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211-219.
- E.J. Cockayne, G. Fricke, C.M. Mynhardt, On a Nordhaus-Gaddum type problem for independent domination, Discrete Math. 138 (1995), 199-205. https://doi.org/10.1016/0012-365X(94)00202-T
- E.J. Cockayne, C.M. Mynhardt, On the product of upper irredundance numbers of a graph and its complement, Discrete Math. 76 (1989), 117-121. https://doi.org/10.1016/0012-365X(89)90304-X
- P. Dorbec, M.A. Henning, D.F. Rall, On the upper total domination number of Cartesian products of graphs, J. Comb. Optim. 16 (2008), 68-80. https://doi.org/10.1007/s10878-007-9099-8
- J.E. Dunbar, T.W. Haynes, S.T. Hedetniemi, Nordhaus-Gaddum bounds for domination sums in graphs with specified minimum degree, Util. Math. 67 (2005), 97-105.
- W. Goddard, M.A. Henning, Nordhaus-Gaddum bounds for independent domination, Discrete Math. 268 (2003), 299-302. https://doi.org/10.1016/S0012-365X(03)00032-3
- W. Goddard, M.A. Henning, H.C. Swart, Some Nordhaus-Gaddum type results, J. Graph Theory 16 (1992), 221-231. https://doi.org/10.1002/jgt.3190160305
- F. Harary, T.W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Math. 155 (1996), 99-105. https://doi.org/10.1016/0012-365X(94)00373-Q
- T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Topics in Domination in Graphs, Developments in Mathematics, vol. 64, Springer, Cham, 2020.
- T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs, Developments in Mathematics, vol. 66, Springer, Cham, 2021.
- T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Domination in Graphs: Core Concepts, Developments in Mathematics, Springer, Cham, 2022.
- M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013.
- M.A. Henning, E.J. Joubert, J. Southey, Nordhaus-Gaddum bounds for total domination, Appl. Math. Lett. 24 (2011), 987-990. https://doi.org/10.1016/j.aml.2011.01.011
- F. Jaeger, C. Payan, Relations du type Nordhaus-Gaddum pour le nombre d'absorption d'un graphe simple, C. R. Acad. Sci. Paris Sér. A 274 (1972), 728-730.
- E.A. Nordhaus, J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175-177. https://doi.org/10.2307/2306658
- L. Volkmann, Nordhaus-Gaddum bounds for domination sums of graphs with minimum degree at least two or three, Util. Math. 82 (2010), 3-9.
- L. Volkmann, Nordhaus-Gaddum type results for domination sums in graphs with minimum degree at least four, five or six, Util. Math. 85 (2011), 113-127.
- Teresa W. Haynes (corresponding author)
- East Tennessee State University, Department of Mathematics and Statistics, Johnson City, TN 37614-0002 USA
- University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South Africa
- Michael A. Henning
- University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South Africa
- Communicated by Dalibor Fronček.
- Received: 2022-01-19.
- Revised: 2022-03-29.
- Accepted: 2022-03-31.
- Published online: 2022-06-30.
