# Graphs with disjoint dominating and paired-dominating sets

Open Mathematics (2010)

• Volume: 8, Issue: 3, page 459-467
• ISSN: 2391-5455

top

## Abstract

top
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.

## How to cite

top

Justin Southey, and Michael Henning. "Graphs with disjoint dominating and paired-dominating sets." Open Mathematics 8.3 (2010): 459-467. <http://eudml.org/doc/269391>.

@article{JustinSouthey2010,
abstract = {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.},
author = {Justin Southey, Michael Henning},
journal = {Open Mathematics},
keywords = {Domination; Paired-domination; Vertex partition; Cubic graph; domination; paired-domination; vertex partition; cubic graph},
language = {eng},
number = {3},
pages = {459-467},
title = {Graphs with disjoint dominating and paired-dominating sets},
url = {http://eudml.org/doc/269391},
volume = {8},
year = {2010},
}

TY - JOUR
AU - Justin Southey
AU - Michael Henning
TI - Graphs with disjoint dominating and paired-dominating sets
JO - Open Mathematics
PY - 2010
VL - 8
IS - 3
SP - 459
EP - 467
AB - 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.
LA - eng
KW - Domination; Paired-domination; Vertex partition; Cubic graph; domination; paired-domination; vertex partition; cubic graph
UR - http://eudml.org/doc/269391
ER -

## References

top
1. [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) Zbl1133.05314
2. [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 Zbl1124.05070
3. [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 Zbl1193.05123
4. [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 Zbl1125.05072
5. [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 Zbl1054.05074
6. [6] Fitzpatrick S., Hartnell B., Paired-domination, Discuss. Math. Graph Theory, 1998, 18(1), 63–72
7. [7] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998 Zbl0890.05002
8. [8] Haynes T.W., Hedetniemi S.T., Slater P.J. (eds), Domination in Graphs. Advanced Topics, Marcel Dekker, New York, 1998 Zbl0883.00011
9. [9] Haynes T.W., Henning M.A., Trees with large paired-domination number, Util. Math., 2006, 71, 3–12 Zbl1112.05078
10. [10] Haynes T.W., Slater P.J., Paired-domination and the paired-domatic number, Congr. Numer., 1995, 109, 65–72 Zbl0904.05052
11. [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. [12] Henning M.A., Trees with equal total domination and paired-domination numbers, Util. Math., 2006, 69, 207–218 Zbl1100.05070
13. [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 Zbl1108.05069
14. [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 Zbl1219.05121
15. [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 Zbl1122.05071
16. [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 Zbl1174.05093
17. [17] Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162 Zbl1224.05370
18. [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 Zbl1168.05348
19. [19] Henning M.A., Vestergaard P.D., Trees with paired-domination number twice their domination number, Util. Math., 2007, 74, 187–197 Zbl1181.05070
20. [20] Ore O., Theory of graphs, American Mathematical Society, Providence, 1962
21. [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 Zbl1013.05055
22. [22] Zelinka B., Total domatic number and degrees of vertices of a graph, Math. Slovaca, 1989, 39(4), 7–11 Zbl0688.05066
23. [23] Zelinka B., Domatic numbers of graphs and their variants: a survey, In: Domination in Graphs, Marcel Dekker, New York, 1998, 351–377 Zbl0894.05026

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.