Dominating and total dominating partitions in cubic graphs

Justin Southey; Michael Henning

Open Mathematics (2011)

  • Volume: 9, Issue: 3, page 699-708
  • ISSN: 2391-5455

Abstract

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

How to cite

top

Justin Southey, and Michael Henning. "Dominating and total dominating partitions in cubic graphs." Open Mathematics 9.3 (2011): 699-708. <http://eudml.org/doc/269432>.

@article{JustinSouthey2011,
abstract = {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.},
author = {Justin Southey, Michael Henning},
journal = {Open Mathematics},
keywords = {Total domination; Cubic graphs; Vertex partition; Hypergraph transversal; total domination; cubic graphs; vertex partition; hypergraph transversal},
language = {eng},
number = {3},
pages = {699-708},
title = {Dominating and total dominating partitions in cubic graphs},
url = {http://eudml.org/doc/269432},
volume = {9},
year = {2011},
}

TY - JOUR
AU - Justin Southey
AU - Michael Henning
TI - Dominating and total dominating partitions in cubic graphs
JO - Open Mathematics
PY - 2011
VL - 9
IS - 3
SP - 699
EP - 708
AB - 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.
LA - eng
KW - Total domination; Cubic graphs; Vertex partition; Hypergraph transversal; total domination; cubic graphs; vertex partition; hypergraph transversal
UR - http://eudml.org/doc/269432
ER -

References

top
  1. [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 Zbl1041.05057
  2. [2] Dankelmann P., Calkin N.J., The domatic number of regular graphs, Ars Combin., 2004, 73, 247–255 Zbl1073.05046
  3. [3] Chvátal V., McDiarmid C., Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26 http://dx.doi.org/10.1007/BF01191201 Zbl0776.05080
  4. [4] Domke G.S., Dunbar J.E., Markus L.R., The inverse domination number of a graph, Ars Combin., 2004, 72, 149–160 Zbl1077.05072
  5. [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 Zbl0945.05047
  6. [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 Zbl1021.05072
  7. [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 Zbl1249.05282
  8. [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 Zbl0890.05002
  9. [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 Zbl0883.00011
  10. [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 Zbl1171.05038
  11. [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. [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 Zbl1214.05106
  13. [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 Zbl1217.05179
  14. [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 Zbl1208.05099
  15. [15] Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162 Zbl1224.05370
  16. [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 Zbl1168.05348
  17. [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 Zbl1180.05080
  18. [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 Zbl1211.05091
  19. [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 Zbl1189.05131
  20. [20] Henning M.A., Yeo A., 2-colorings in k-regular k-uniform hypergraphs, manuscript Zbl1292.05112
  21. [21] Kulli V.R., Sigarkanti S.C., Inverse domination in graphs, Nat. Acad. Sci. Lett., 1991, 14(12), 473–475 Zbl0906.05038
  22. [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 Zbl1219.05125
  23. [23] Ore Ø., Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38, American Math. Society, Providence, 1962 
  24. [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 Zbl0299.05122
  25. [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 Zbl1164.05052
  26. [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. [27] Zelinka B., Total domatic number and degrees of vertices of a graph, Math. Slovaca, 1989, 39(1), 7–11 Zbl0688.05066
  28. [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 Zbl0894.05026

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.