Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

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

  • University of Johannesburg
  • University of Johannesburg

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ć.