Article in volume
Authors:
Title:
Minimal graphs with disjoint dominating and total dominating sets
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 47-74
Received: 2021-02-23 , Revised: 2021-09-19 , Accepted: 2021-09-19 , Available online: 2021-09-28 , https://doi.org/10.7151/dmgt.2433
Abstract:
A graph $G$ is a DTDP-graph if it has a pair $(D,T)$ of disjoint sets of
vertices of $G$ such that $D$ is a dominating set and $T$ is a total dominating
set of $G$. Such graphs were studied in a number of research papers. In this
paper we study further properties of DTDP-graphs and, in particular, we
characterize minimal DTDP-graphs without loops.
Keywords:
domination, total domination
References:
- I. Broere, M. Dorfling, W. Goddard, J.H. Hattingh, M.A. Henning and E. Ungerer, Augmenting trees to have two disjoint total dominating sets, Bull. Inst. Combin. Appl. 42 (2004) 12–18.
- P. Delgado, W.J. Desormeaux and T.W. Haynes, Partitioning the vertices of a graph into two total dominating sets, Quaest. Math. 39 (2016) 863–873.
https://doi.org/10.2989/16073606.2016.1188862 - W.J. Desormeaux, T.W. Haynes and M.A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017) 52–63.
https://doi.org/10.1016/j.dam.2017.01.032 - M. Dorfling, W. Goddard, J.H. Hattingh and 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 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Eds), Topics in Domination in Graphs (Dev. Math. 64, Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Eds), Structures of Domination in Graphs (Dev. Math. 66, Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - P. Heggernes and J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998) 128–142.
- M.A. Henning, C. Löwenstein and 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 and 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 and A.J. Marcon, Semitotal domination in graphs: Partition and algorithmic results, Util. Math. 106 (2018) 165–184.
- M.A. Henning and 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 and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159–162.
- M.A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009) 119–129.
https://doi.org/10.2989/QM.2009.32.1.10.712 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monogr. Math., Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - E.M. Kiunisala and F.P. Jamil, On pairs of disjoint dominating sets in a graph, Int. J. Math. Anal. 10 (2016) 623–637.
https://doi.org/10.12988/ijma.2016.6343 - O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, Amer. Math. Soc., Providence, 1962).
- J. Southey and M.A. Henning, Dominating and total dominating partitions in cubic graphs, Cent. Eur. J. Math. 9 (2011) 699–708.
https://doi.org/10.2478/s11533-011-0014-2
Close