Opuscula Mathematica
Opuscula Math. 42, no. 4 (2022), 573-582

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.
Full text (pdf)
References ▼
  1. [1] 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
  2. [2] E.J. Cockayne, R.M. Dawes, S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211-219.
  3. [3] 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
  4. [4] 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
  5. [5] 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
  6. [6] 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.
  7. [7] 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
  8. [8] 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
  9. [9] 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
  10. [10] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Topics in Domination in Graphs, Developments in Mathematics, vol. 64, Springer, Cham, 2020.
  11. [11] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs, Developments in Mathematics, vol. 66, Springer, Cham, 2021.
  12. [12] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Domination in Graphs: Core Concepts, Developments in Mathematics, Springer, Cham, 2022.
  13. [13] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013.
  14. [14] 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
  15. [15] 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.
  16. [16] E.A. Nordhaus, J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175-177. https://doi.org/10.2307/2306658
  17. [17] L. Volkmann, Nordhaus-Gaddum bounds for domination sums of graphs with minimum degree at least two or three, Util. Math. 82 (2010), 3-9.
  18. [18] 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.
About the authors ▼
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
About the article ▼
Communicated by Dalibor Fronček.
Received: 2022-01-19.
Revised: 2022-03-29.
Accepted: 2022-03-31.
Published online: 2022-06-30.
Cite this article as ▼
Teresa W. Haynes, Michael A. Henning, Nordhaus-Gaddum bounds for upper total domination, Opuscula Math. 42, no. 4 (2022), 573-582, https://doi.org/10.7494/OpMath.2022.42.4.573.
Download this article's citation as: