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.

Full text (pdf)

  1. 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
  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. https://doi.org/10.1016/j.disc.2005.06.020
  7. 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
  8. W. Goddard, M.A. Henning, Thoroughly dispersed colorings, J. Graph Theory 88 (2017), 174-191. https://doi.org/10.1002/jgt.22204
  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. https://doi.org/10.1007/978-3-030-58892-2
  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. https://doi.org/10.7151/dmgt.1514
  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. https://doi.org/10.1016/j.dam.2010.06.004
  15. 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
  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. https://doi.org/10.2989/QM.2009.32.1.10.712
  18. 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
  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. https://doi.org/10.1007/978-1-4614-6525-6_13
  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. https://doi.org/10.2478/s11533-011-0014-2
  25. 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.
Opuscula Mathematica - cover

Cite this article as:
Teresa W. Haynes, Michael A. Henning, Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set, Opuscula Math. 44, no. 4 (2024), 543-563, https://doi.org/10.7494/OpMath.2024.44.4.543

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.