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.
@article{bwmeta1.element.doi-10_2478_s11533-011-0014-2,
author = {Justin Southey and Michael Henning},
title = {Dominating and total dominating partitions in cubic graphs},
journal = {Open Mathematics},
volume = {9},
year = {2011},
pages = {699-708},
zbl = {1233.05151},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0014-2}
}
Justin Southey; Michael Henning. Dominating and total dominating partitions in cubic graphs. Open Mathematics, Tome 9 (2011) pp. 699-708. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0014-2/
[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 | Zbl 1041.05057
[2] Dankelmann P., Calkin N.J., The domatic number of regular graphs, Ars Combin., 2004, 73, 247–255 | Zbl 1073.05046
[3] Chvátal V., McDiarmid C., Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26 http://dx.doi.org/10.1007/BF01191201 | Zbl 0776.05080
[4] Domke G.S., Dunbar J.E., Markus L.R., The inverse domination number of a graph, Ars Combin., 2004, 72, 149–160 | Zbl 1077.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 | Zbl 0945.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 | Zbl 1021.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 | Zbl 1249.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 | Zbl 0890.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 | Zbl 0883.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 | Zbl 1171.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 | Zbl 1214.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 | Zbl 1217.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 | Zbl 1208.05099
[15] Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162 | Zbl 1224.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 | Zbl 1168.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 | Zbl 1180.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 | Zbl 1211.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 | Zbl 1189.05131
[20] Henning M.A., Yeo A., 2-colorings in k-regular k-uniform hypergraphs, manuscript | Zbl 1292.05112
[21] Kulli V.R., Sigarkanti S.C., Inverse domination in graphs, Nat. Acad. Sci. Lett., 1991, 14(12), 473–475 | Zbl 0906.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 | Zbl 1219.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 | Zbl 0299.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 | Zbl 1164.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 | Zbl 0688.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 | Zbl 0894.05026