Geodesic
Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 827-847.

Voir la notice de l'article provenant de la source Library of Science

A subset D ⊆ VG is a dominating set of G if every vertex in VG – D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP -graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP -graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459–467; J. Comb. Optim. 22 (2011) 217–234]. In this paper, we provide conditions which ensure that a graph is a DPDP -graph. In particular, we characterize the minimal DPDP -graphs.
Keywords: domination, paired-domination 
@article{DMGT_2021_41_3_a8,
     author = {Henning, Michael A. and Topp, Jerzy},
     title = {Minimal {Graphs} with {Disjoint} {Dominating} and {Paired-Dominating} {Sets}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {827--847},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a8/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Topp, Jerzy
TI  - Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 827
EP  - 847
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a8/
LA  - en
ID  - DMGT_2021_41_3_a8
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Topp, Jerzy
%T Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 827-847
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a8/
%G en
%F DMGT_2021_41_3_a8
Henning, Michael A.; Topp, Jerzy. Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 827-847. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a8/

[1] V. Anusuya and R. Kala, A note on disjoint dominating sets in graphs, Int. J. Contemp. Math. Sci. 7 (2012) 2099–2110.

[2] 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.

[3] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (CRC Press, Boca Raton, 2016)

[4] 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. doi:10.2989/16073606.2016.1188862

[5] 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. doi:10.1016/j.dam.2017.01.032

[6] 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. doi:10.1016/j.disc.2005.06.020

[7] T.W. Haynes and M.A. Henning, Trees with two disjoint minimum independent dominating sets, Discrete Math. 304 (2005) 69–78. doi:10.1016/j.disc.2005.09.012

[8] S.M. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, L. Markus and P.J. Slater, Disjoint dominating sets in graphs, in: Proc. ICDM 2006, Ramanujan Math. Soc. Lect. Notes Ser. 7 (2008) 87–100.

[9] P. Heggernes and J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1988) 128–142.

[10] M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451–6458. doi:10.1016/j.disc.2009.06.017

[11] 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. doi:10.7151/dmgt.1514

[12] M.A. Henning, C. Löwenstein and D. Rautenbach, An independent dominating set in the complement of a minimum dominating set of a tree, Appl. Math. Lett. 23 (2010) 79–81. doi:10.1016/j.aml.2009.08.008

[13] 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. doi:10.1016/j.dam.2010.06.004

[14] M.A. Henning and A.J. Marcon, Semitotal domination in graphs: Partition and algorithmic results, Util. Math. 106 (2018) 165–184.

[15] M.A. Henning and D.F. Rall, On graphs with disjoint dominating and 2 -dominating sets, Discuss. Math. Graph Theory 33 (2013) 139–146. doi:10.7151/dmgt.1652

[16] M.A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159–162.

[17] M.A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009) 119–129. doi:10.2989/QM.2009.32.1.10.712

[18] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, Springer, 2013). doi:10.1007/978-1-4614-6525-6

[19] E.M. Kiunisala and F.P. Jamil, On pairs of disjoint dominating sets in a graph, Int. J. Math. Anal. 10 (2016) 623–637. doi:10.12988/ijma.2016.6343

[20] V.R. Kulli and S.C. Sigarkanti, Inverse domination in graphs, Nat. Acad. Sci. Lett. 14 (1991) 473–475.

[21] C. Löwenstein and D. Rautenbach, Pairs of disjoint dominating sets and the minimum degree of graphs, Graphs Combin. 26 (2010) 407–424. doi:10.1007/s00373-010-0918-9

[22] M. Miotk, J. Topp and P. Żyliński, Disjoint dominating and 2 -dominating sets in graphs, Discrete Optim. 35 (2020) 100553. doi:10.1016/j.disopt.2019.100553

[23] O. Ore, Theory of Graphs (Providence, RI, 1962).

[24] J. Southey and M.A. Henning, Graphs with disjoint dominating and paired-dominating sets, Cent. Eur. J. Math. 8 (2010) 459–467. doi:10.2478/s11533-010-0033-4

[25] J. Southey and M.A. Henning, Dominating and total dominating partitions in cubic graphs, Cent. Eur. J. Math. 9 (2011) 699–708. doi:10.2478/s11533-011-0014-2

[26] J. Southey and M.A. Henning, A characterization of graphs with disjoint dominating and paired-dominating sets, J. Comb. Optim. 22 (2011) 217–234. doi:10.1007/s10878-009-9274-1