Nordhaus-Gaddum bounds for upper total domination

• Autorzy: Haynes Teresa W. , Henning Michael A.

Identyfikatory

DOI

10.7494/OpMath.2022.42.4.573

• Języki publikacji: EN

Abstrakty

EN

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)2, and these bounds are tight.

Słowa kluczowe

EN

upper total domination; Nordhaus-Gaddum bound

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2022
• Tom: Vol. 42, no. 4
• Strony: 573--582
• Opis fizyczny: Bibliogr. 18 poz., tab.

Twórcy

autor

Haynes Teresa W.

• 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

autor

Henning Michael A.

• University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South Africa

Bibliografia

• [1] M. Aouchiche, P. Hansen, A survey of Nordhaus–Gaddum type relations, Discrete Appl. Math. 161 (2013), 466–546.
• [2] E.J. Cockayne, R.M. Dawes, S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211–219.
• [3] E.J. Cockayne, G. Fricke, C.M. Mynhardt, On a Nordhaus–Gaddum type problem for independent domination, Discrete Math. 138 (1995), 199–205.
• [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.
• [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.
• [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] W. Goddard, M.A. Henning, Nordhaus–Gaddum bounds for independent domination, Discrete Math. 268 (2003), 299–302.
• [8] W. Goddard, M.A. Henning, H.C. Swart, Some Nordhaus–Gaddum type results, J. Graph Theory 16 (1992), 221–231.
• [9] F. Harary, T.W. Haynes, Nordhaus–Gaddum inequalities for domination in graphs, Discrete Math. 155 (1996), 99–105.
• [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] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs, Developments in Mathematics, vol. 66, Springer, Cham, 2021.
• [12] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Domination in Graphs: Core Concepts, Developments in Mathematics, Springer, Cham, 2022.
• [13] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013.
• [14] M.A. Henning, E.J. Joubert, J. Southey, Nordhaus–Gaddum bounds for total domination, Appl. Math. Lett. 24 (2011), 987–990.
• [15] F. Jaeger, C. Payan, Relations du type Nordhaus–Gaddum pour le nombre d’absorption d’un graphe simple, C.R. Acad. Sci. Paris A, 274 (1972), 728–730.
• [16] E.A. Nordhaus, J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175–177.
• [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] 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.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).