PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2011 | 9 | 3 | 699-708
Tytuł artykułu

Dominating and total dominating partitions in cubic graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In this paper, we continue the study of domination and total domination in cubic graphs. It is known [Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162] that every cubic graph has a dominating set and a total dominating set which are disjoint. In this paper we show that every connected cubic graph on nvertices has a total dominating set whose complement contains a dominating set such that the cardinality of the total dominating set is at most (n+2)/2, and this bound is essentially best possible.
Wydawca
Czasopismo
Rocznik
Tom
9
Numer
3
Strony
699-708
Opis fizyczny
Daty
wydano
2011-06-01
online
2011-03-22
Twórcy
Bibliografia
  • [1] Archdeacon D., Ellis-Monaghan J., Fisher D., Froncek D., Lam P.C.B., Seager S., Wei B., Yuster R., Some remarks on domination, J. Graph Theory, 2004, 46(3), 207–210 http://dx.doi.org/10.1002/jgt.20000
  • [2] Dankelmann P., Calkin N.J., The domatic number of regular graphs, Ars Combin., 2004, 73, 247–255
  • [3] Chvátal V., McDiarmid C., Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26 http://dx.doi.org/10.1007/BF01191201
  • [4] Domke G.S., Dunbar J.E., Markus L.R., The inverse domination number of a graph, Ars Combin., 2004, 72, 149–160
  • [5] Favaron O., Henning M.A., Mynhart* C.M., Puech J., Total domination in graphs with minimum degree three, J. Graph Theory, 2000, 34(1), 9–19 http://dx.doi.org/10.1002/(SICI)1097-0118(200005)34:1<9::AID-JGT2>3.0.CO;2-O
  • [6] Feige U., Halldórsson M.M., Kortsarz G., Srinivasan A., Approximating the domatic number, SIAM J. Comput., 2002, 32(1), 172–195 http://dx.doi.org/10.1137/S0097539700380754
  • [7] Frendrup A., Henning M.A., Randerath B., Vestergaard P.D., On a conjecture about inverse domination in graphs, Ars Combin., 2010, 97A, 129–143
  • [8] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals of Domination in Graphs, Pure Appl. Math. (N.Y.), 208, Marcel Dekker, New York, 1998
  • [9] Haynes T.W., Hedetniemi S.T., Slater P.J. (Eds.), Domination in Graphs: Advanced Topics, Pure Appl. Math. (N.Y.), 209, Marcel Dekker, New York, 1998
  • [10] Hedetniemi S.M., Hedetniemi S.T., Laskar R.C., Markus L., Slater P.J., Disjoint dominating sets in graphs, International Conference on Discrete Mathematics, Bangalore, December 15, 18, 2006, Ramanujan Math. Soc. Lect. Notes Ser., 7, Ramanujan Math. Soc., Mysore, 2008, 87–100
  • [11] Henning MA, Lbwenstein C., Rautenbach D., Remarks about disjoint dominating sets, Discrete Math., 2009, 309(23–24), 6451–6458 http://dx.doi.org/10.1016/j.disc.2009.06.017
  • [12] Henning M.A., Löwenstein C., Rautenbach D., An independent dominating set in the complement of a minimum dominating set of a tree, Appl. Math. Lett., 2010, 23(1), 79–81 http://dx.doi.org/10.1016/j.aml.2009.08.008
  • [13] Henning M.A., Löwenstein C., Rautenbach D., Partitioning a graph into a dominating set, a total dominating set, and something else, Discuss. Math. Graph Theory, 2010, 30(4), 563–574
  • [14] Henning M.A., Löwenstein C., Rautenbach D., Southey J., Disjoint dominating and total dominating sets in graphs, Discrete Appl. Math., 2010, 158(15), 1615–1623 http://dx.doi.org/10.1016/j.dam.2010.06.004
  • [15] Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162
  • [16] 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
  • [17] Henning M.A., Yeo A., Total domination in graphs with given girth, Graphs Combin., 2008, 24(4), 333–348 http://dx.doi.org/10.1007/s00373-008-0797-5
  • [18] Henning M.A., Yeo A., Hypergraphs with large transversal number and with edge sizes at least 3, J. Graph Theory, 2008, 59(4), 326–348
  • [19] Henning M.A., Yeo A., Total domination in 2-connected graphs and in graphs with no induced 6-cycles, J. Graph Theory, 2009, 60(1), 55–79 http://dx.doi.org/10.1002/jgt.20345
  • [20] Henning M.A., Yeo A., 2-colorings in k-regular k-uniform hypergraphs, manuscript
  • [21] Kulli V.R., Sigarkanti S.C., Inverse domination in graphs, Nat. Acad. Sci. Lett., 1991, 14(12), 473–475
  • [22] Löwenstein C., Rautenbach D., Pairs of disjoint dominating sets and the minimum degree of graphs, Graphs Combin., 2010, 26(3), 407–424 http://dx.doi.org/10.1007/s00373-010-0918-9
  • [23] Ore Ø., Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38, American Math. Society, Providence, 1962
  • [24] Seymour P.D., On the two-colouring of hypergraphs, Q. J. Math., 1974, 25(1), 303–312 http://dx.doi.org/10.1093/qmath/25.1.303
  • [25] Thomassé S., Yeo A., Total domination of graphs and small transversals of hypergraphs, Combinatorica, 2007, 27(4), 473–487 http://dx.doi.org/10.1007/s00493-007-2020-3
  • [26] Tuza Z., Covering all cliques of a graph, Discrete Math., 1990, 86(1–3), 117–126 http://dx.doi.org/10.1016/0012-365X(90)90354-K
  • [27] Zelinka B., Total domatic number and degrees of vertices of a graph, Math. Slovaca, 1989, 39(1), 7–11
  • [28] Zelinka B., Domatic numbers of graphs and their variants: a survey, In: Domination in Graphs: Advanced Topics, Pure Appl. Math. (N.Y.), 209, Marcel Dekker, New York, 351–377
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-011-0014-2
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ć.