Graphs with disjoint dominating and paired-dominating sets

• Autorzy: Justin Southey , Michael Henning
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Domination; Paired-domination; Vertex partition; Cubic graph

Kategorie tematyczne

• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2010
• Tom: 8
• Numer: 3
• Strony: 459-467

Daty

wydano

2010-06-01

online

2010-05-30

Twórcy

autor

Justin Southey

• University of Johannesburg

autor

Michael Henning

• University of Johannesburg

Bibliografia

• [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)
• [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
• [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
• [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
• [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
• [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
• [8] Haynes T.W., Hedetniemi S.T., Slater P.J. (eds), Domination in Graphs. Advanced Topics, Marcel Dekker, New York, 1998
• [9] Haynes T.W., Henning M.A., Trees with large paired-domination number, Util. Math., 2006, 71, 3–12
• [10] Haynes T.W., Slater P.J., Paired-domination and the paired-domatic number, Congr. Numer., 1995, 109, 65–72
• [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
• [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
• [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
• [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
• [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
• [17] Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162
• [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
• [19] Henning M.A., Vestergaard P.D., Trees with paired-domination number twice their domination number, Util. Math., 2007, 74, 187–197
• [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
• [22] Zelinka B., Total domatic number and degrees of vertices of a graph, Math. Slovaca, 1989, 39(4), 7–11
• [23] Zelinka B., Domatic numbers of graphs and their variants: a survey, In: Domination in Graphs, Marcel Dekker, New York, 1998, 351–377

Identyfikatory

DOI

10.2478/s11533-010-0033-4