Graphs with disjoint dominating and paired-dominating sets. (English) Zbl 1215.05126

Summary: 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.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI


[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 · Zbl 0916.05061
[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. · 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 · Zbl 0105.35401
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.