# 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

## Access Full Article

top## Abstract

top## How to cite

topJustin 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] 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] Dankelmann P., Calkin N.J., The domatic number of regular graphs, Ars Combin., 2004, 73, 247–255 Zbl1073.05046
- [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] 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] 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] 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] 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] 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] 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] 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] 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 Zbl1214.05106
- [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] 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] 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] 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] 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] 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] 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] Henning M.A., Yeo A., 2-colorings in k-regular k-uniform hypergraphs, manuscript Zbl1292.05112
- [21] Kulli V.R., Sigarkanti S.C., Inverse domination in graphs, Nat. Acad. Sci. Lett., 1991, 14(12), 473–475 Zbl0906.05038
- [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] 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 Zbl0299.05122
- [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] 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 Zbl0688.05066
- [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 ?

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