Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set

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

Identyfikatory

DOI

10.7494/OpMath.2024.44.4.543

• Języki publikacji: EN

Abstrakty

EN

A graph G whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. We give constructions that yield infinite families of graphs that are TI-graphs, as well as constructions that yield infinite families of graphs that are not TI-graphs. We study regular graphs that are TI-graphs. Among other results, we prove that all toroidal graphs are TI-graphs.

Słowa kluczowe

EN

total domination; vertex partitions; independent domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2024
• Tom: Vol. 44, no. 4
• Strony: 543--563
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Haynes Teresa W.

• East Tennessee State University, Department of Mathematics and Statistics, Johnson City, TN 37614–0002, USA

autor

Henning Michael A.

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

Bibliografia

• [1] N. Alon, Z. Bregman, Every 8-uniform 8-regular hypergraph is 2-colorable, Graphs Combin. 4 (1988), 303–306.
• [2] D.W. Bange, A.E. Barkauskas, P.J. Slater, Disjoint Dominating Sets in Trees, Sandia Laboratories Rept. SAND-78-1087J, 1978.
• [3] E.J. Cockayne, R.M. Dawes, S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211–219.
• [4] P. Delgado, W.J. Desormeaux, T.W. Haynes, Partitioning the vertices of a graph into a total dominating set and an independent dominating set, Ars Combin. 144 (2019), 367–379.
• [5] W.J. Desormeaux, T.W. Haynes, M.A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017), 52–63.
• [6] M. Dorfling, W. Goddard, J.H. Hattingh, M.A. Henning, Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets, Discrete Math. 300 (2005), 82–90.
• [7] W. Goddard, M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), 839–854.
• [8] W. Goddard, M.A. Henning, Thoroughly dispersed colorings, J. Graph Theory 88 (2017), 174–191.
• [9] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Topics in Domination in Graphs, Series: Developments in Mathematics, vol. 64, Springer, Cham, 2020.
• [10] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs, Series: Developments in Mathematics, vol. 66, Springer, Cham, 2021.
• [11] T.W. Haynes, S.T. Hedetniemi, M. A. Henning, Domination in Graphs: Core Concepts, Series: Springer Monographs in Mathematics, Springer, Cham, 2023.
• [12] P. Heggernes, J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998), 128–142.
• [13] M.A. Henning, C. Löwenstein, D. Rautenbach, Partitioning a graph into a dominating set, a total dominating set, and something else, Discuss. Math. Graph Theory 30 (2010), 563–574.
• [14] M.A. Henning, C. Löwenstein, D. Rautenbach, J. Southey, Disjoint dominating and total dominating sets in graphs, Discrete Appl. Math. 158 (2010), 1615–1623.
• [15] M.A. Henning, I. Peterin, A characterization of graphs with disjoint total dominating sets, Ars Math. Contemp. 16 (2019), 359–375.
• [16] M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008), 159–162.
• [17] M.A. Henning, J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009), no. 1, 119–129.
• [18] M.A. Henning, A. Yeo, 2-Colorings in k-regular k-uniform hypergraphs, European J. Combin. 34 (2013), 1192–1202.
• [19] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, Cham, New York, 2013.
• [20] M.A. Henning, A. Yeo, Graphs with disjoint total dominating sets, [in:] Total Domination in Graphs, Springer Monographs in Mathematics, (2013), 109–118.
• [21] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Pub., vol. 38, Providence, RI, 1962.
• [22] P.D. Seymour, On the two coloring of hypergraphs, Quart. J. Math. Oxford Ser. 25 (1974), 303–312.
• [23] J. Southey, Domination results: vertex partitions and edge weight functions, PhD Thesis, Univ. Johannesburg, May 2012.
• [24] J. Southey, M.A. Henning, Dominating and total dominating partitions in cubic graphs, Open Math. 9 (2011), 699–708.
• [25] C. Thomassen, The even cycle problem for directed graphs, J. Amer. Math. Soc. 5 (1992), 217–229.

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)