A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a dominating set such that the subgraph induced by the dominating set contains a perfect matching. In this paper, we show that no minimum degree is sufficient to guarantee the existence of a disjoint dominating set and a paired-dominating set. However, we prove that the vertex set of every cubic graph can be partitioned into a dominating set and a paired-dominating set.
@article{bwmeta1.element.doi-10_2478_s11533-010-0033-4,
author = {Justin Southey and Michael Henning},
title = {Graphs with disjoint dominating and paired-dominating sets},
journal = {Open Mathematics},
volume = {8},
year = {2010},
pages = {459-467},
zbl = {1215.05126},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0033-4}
}
Justin Southey; Michael Henning. Graphs with disjoint dominating and paired-dominating sets. Open Mathematics, Tome 8 (2010) pp. 459-467. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0033-4/
[1] Chen X.G., Sun L., Xing H.M., Paired-domination numbers of cubic graphs, Acta Math. Sci. Ser. A Chin. Ed., 2007, 27(1), 166–170 (in Chinese) | Zbl 1133.05314
[2] Cheng T.C.E., Kang L.Y., Ng C.T., Paired domination on interval and circular-arc graphs, Discrete Appl. Math., 2007, 155(16), 2077–2086 http://dx.doi.org/10.1016/j.dam.2007.05.011 | Zbl 1124.05070
[3] Dorbec P., Gravier S., Paired-domination in P 5-free graphs, Graphs Combin., 2008, 24(4), 303–308. http://dx.doi.org/10.1007/s00373-008-0792-x | Zbl 1193.05123
[4] Dorbec P., Gravier S., Henning M.A., Paired-domination in generalized claw-free graphs, J. Comb. Optim., 2007, 14(1), 1–7 http://dx.doi.org/10.1007/s10878-006-9022-8 | Zbl 1125.05072
[5] Favaron O., Henning M.A., Paired domination in claw-free cubic graphs, Graphs Combin., 2004, 20(4), 447–456 http://dx.doi.org/10.1007/s00373-004-0577-9 | Zbl 1054.05074
[6] Fitzpatrick S., Hartnell B., Paired-domination, Discuss. Math. Graph Theory, 1998, 18(1), 63–72
[7] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998 | Zbl 0890.05002
[8] Haynes T.W., Hedetniemi S.T., Slater P.J. (eds), Domination in Graphs. Advanced Topics, Marcel Dekker, New York, 1998 | Zbl 0883.00011
[9] Haynes T.W., Henning M.A., Trees with large paired-domination number, Util. Math., 2006, 71, 3–12 | Zbl 1112.05078
[10] Haynes T.W., Slater P.J., Paired-domination and the paired-domatic number, Congr. Numer., 1995, 109, 65–72 | Zbl 0904.05052
[11] Haynes T.W., Slater P.J., Paired-domination in graphs, Networks, 1998, 32(3), 199–206 http://dx.doi.org/10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
[12] Henning M.A., Trees with equal total domination and paired-domination numbers, Util. Math., 2006, 69, 207–218 | Zbl 1100.05070
[13] Henning M.A., Graphs with large paired-domination number, J. Combin. Optim., 2007, 13(1), 61–78 http://dx.doi.org/10.1007/s10878-006-9014-8 | Zbl 1108.05069
[14] Henning M.A., A survey of selected recent results on total domination in graphs, Discrete Math., 2009, 309(1), 32–63 http://dx.doi.org/10.1016/j.disc.2007.12.044 | Zbl 1219.05121
[15] Henning M.A., Plummer M.D., Vertices contained in all or in no minimum paired-dominating set of a tree, J. Combin. Optim., 2005, 10(3), 283–294 http://dx.doi.org/10.1007/s10878-005-4107-3 | Zbl 1122.05071
[16] Henning M.A., Mynhardt C.M., The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., 2008, 58(4), 887–897 http://dx.doi.org/10.1007/s10587-008-0057-0 | Zbl 1174.05093
[17] Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162 | Zbl 1224.05370
[18] Henning M.A., Southey J., A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math., 2009, 32(1), 119–129 http://dx.doi.org/10.2989/QM.2009.32.1.10.712 | Zbl 1168.05348
[19] Henning M.A., Vestergaard P.D., Trees with paired-domination number twice their domination number, Util. Math., 2007, 74, 187–197 | Zbl 1181.05070
[20] Ore O., Theory of graphs, American Mathematical Society, Providence, 1962
[21] Qiao H., Kang L., Cardei M., Du D.Z., Paired-domination of trees, J. Global Optim., 2003, 25(1), 43–54 http://dx.doi.org/10.1023/A:1021338214295 | Zbl 1013.05055
[22] Zelinka B., Total domatic number and degrees of vertices of a graph, Math. Slovaca, 1989, 39(4), 7–11 | Zbl 0688.05066
[23] Zelinka B., Domatic numbers of graphs and their variants: a survey, In: Domination in Graphs, Marcel Dekker, New York, 1998, 351–377 | Zbl 0894.05026