PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2010 | 8 | 3 | 459-467
Tytuł artykułu

Graphs with disjoint dominating and paired-dominating sets

Treść / Zawartość
Warianty tytułu
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
8
Numer
3
Strony
459-467
Opis fizyczny
Daty
wydano
2010-06-01
online
2010-05-30
Twórcy
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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-010-0033-4
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.