Opuscula Math. 44, no. 4 (2024), 543-563
https://doi.org/10.7494/OpMath.2024.44.4.543
Opuscula Mathematica
Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set
Teresa W. Haynes
Michael A. Henning
Abstract. 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.
Keywords: total domination, vertex partitions, independent domination.
Mathematics Subject Classification: 05C69.
- N. Alon, Z. Bregman, Every \(8\)-uniform \(8\)-regular hypergraph is \(2\)-colorable, Graphs Combin. 4 (1988), 303-306. https://doi.org/10.1007/BF01864169
- D.W. Bange, A.E. Barkauskas, P.J. Slater, Disjoint Dominating Sets in Trees, Sandia Laboratories Rept. SAND-78-1087J, 1978.
- E.J. Cockayne, R.M. Dawes, S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211-219.
- 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.
- 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.
- 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. https://doi.org/10.1016/j.disc.2005.06.020
- W. Goddard, M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), 839-854. https://doi.org/10.1016/j.disc.2012.11.031
- W. Goddard, M.A. Henning, Thoroughly dispersed colorings, J. Graph Theory 88 (2017), 174-191. https://doi.org/10.1002/jgt.22204
- T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Topics in Domination in Graphs, Series: Developments in Mathematics, vol. 64, Springer, Cham, 2020.
- T.W. Haynes, S.T. Hedetniemi, M.A. Henning (eds), Structures of Domination in Graphs, Series: Developments in Mathematics, vol. 66, Springer, Cham, 2021. https://doi.org/10.1007/978-3-030-58892-2
- T.W. Haynes, S.T. Hedetniemi, M. A. Henning, Domination in Graphs: Core Concepts, Series: Springer Monographs in Mathematics, Springer, Cham, 2023.
- P. Heggernes, J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998), 128-142.
- 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. https://doi.org/10.7151/dmgt.1514
- 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. https://doi.org/10.1016/j.dam.2010.06.004
- M.A. Henning, I. Peterin, A characterization of graphs with disjoint total dominating sets, Ars Math. Contemp. 16 (2019), 359-375. https://doi.org/10.26493/1855-3974.1525.7f3
- M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008), 159-162.
- M.A. Henning, J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009), no. 1, 119-129. https://doi.org/10.2989/QM.2009.32.1.10.712
- M.A. Henning, A. Yeo, \(2\)-colorings in \(k\)-regular \(k\)-uniform hypergraphs, European J. Combin. 34 (2013), 1192-1202. https://doi.org/10.1016/j.ejc.2013.04.005
- M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, Cham, New York, 2013.
- M.A. Henning, A. Yeo, Graphs with disjoint total dominating sets, [in:] Total Domination in Graphs, Springer Monographs in Mathematics, (2013), 109-118. https://doi.org/10.1007/978-1-4614-6525-6_13
- O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Pub., vol. 38, Providence, RI, 1962.
- P.D. Seymour, On the two coloring of hypergraphs, Quart. J. Math. Oxford Ser. 25 (1974), 303-312.
- J. Southey, Domination results: vertex partitions and edge weight functions, PhD Thesis, Univ. Johannesburg, May 2012.
- J. Southey, M.A. Henning, Dominating and total dominating partitions in cubic graphs, Open Math. 9 (2011), 699-708. https://doi.org/10.2478/s11533-011-0014-2
- C. Thomassen, The even cycle problem for directed graphs, J. Amer. Math. Soc. 5 (1992), 217-229. https://doi.org/10.2307/2152767
- Teresa W. Haynes (corresponding author)
- East Tennessee State University, Department of Mathematics and Statistics, Johnson City, TN 37614-0002, USA
- Michael A. Henning
- University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006, South Africa
- Communicated by Dalibor Fronček.
- Received: 2023-08-30.
- Accepted: 2024-01-08.
- Published online: 2024-04-29.
