# Graphs with disjoint dominating and paired-dominating sets

Justin Southey; Michael Henning

Open Mathematics (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topJustin 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] 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] 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] 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] 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] 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] 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 Zbl0890.05002
- [8] Haynes T.W., Hedetniemi S.T., Slater P.J. (eds), Domination in Graphs. Advanced Topics, Marcel Dekker, New York, 1998 Zbl0883.00011
- [9] Haynes T.W., Henning M.A., Trees with large paired-domination number, Util. Math., 2006, 71, 3–12 Zbl1112.05078
- [10] Haynes T.W., Slater P.J., Paired-domination and the paired-domatic number, Congr. Numer., 1995, 109, 65–72 Zbl0904.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 Zbl1100.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 Zbl1108.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 Zbl1219.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 Zbl1122.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 Zbl1174.05093
- [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] 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] Henning M.A., Vestergaard P.D., Trees with paired-domination number twice their domination number, Util. Math., 2007, 74, 187–197 Zbl1181.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 Zbl1013.05055
- [22] Zelinka B., Total domatic number and degrees of vertices of a graph, Math. Slovaca, 1989, 39(4), 7–11 Zbl0688.05066
- [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 ?

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