# Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning; Christian Löwenstein; Dieter Rautenbach

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 4, page 563-574
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMichael A. Henning, Christian Löwenstein, and Dieter Rautenbach. "Partitioning a graph into a dominating set, a total dominating set, and something else." Discussiones Mathematicae Graph Theory 30.4 (2010): 563-574. <http://eudml.org/doc/270935>.

@article{MichaelA2010,

abstract = {A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.},

author = {Michael A. Henning, Christian Löwenstein, Dieter Rautenbach},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination; total domination; domatic number; vertex partition; Petersen graph; vertex partition, Petersen graph},

language = {eng},

number = {4},

pages = {563-574},

title = {Partitioning a graph into a dominating set, a total dominating set, and something else},

url = {http://eudml.org/doc/270935},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Michael A. Henning

AU - Christian Löwenstein

AU - Dieter Rautenbach

TI - Partitioning a graph into a dominating set, a total dominating set, and something else

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 4

SP - 563

EP - 574

AB - A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

LA - eng

KW - domination; total domination; domatic number; vertex partition; Petersen graph; vertex partition, Petersen graph

UR - http://eudml.org/doc/270935

ER -

## References

top- [1] N.J. Calkin and P. Dankelmann, The domatic number of regular graphs, Ars Combin. 73 (2004) 247-255. Zbl1073.05046
- [2] G.S. Domke, J.E. Dunbar and L.R. Markus, The inverse domination number of a graph, Ars Combin. 72 (2004) 149-160. Zbl1077.05072
- [3] U. Feige, M.M. Halldórsson, G. Kortsarz and A. Srinivasan, Approximating the domatic number, SIAM J. Comput. 32 (2002) 172-195, doi: 10.1137/S0097539700380754. Zbl1021.05072
- [4] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001).
- [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in graphs: Advanced topics (Marcel Dekker, New York, 1998). Zbl0883.00011
- [7] S.M. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, L. Markus and P.J. Slater, Disjoint dominating sets in graphs, in: Proc. Internat. Conf. Discrete Math., ICDM 2006, 87-100, Ramanujan Math. Soc., Lecture Notes Series in Mathematics, 2008. Zbl1171.05038
- [8] M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451-6458, doi: 10.1016/j.disc.2009.06.017. Zbl1189.05130
- [9] M.A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162. Zbl1224.05370
- [10] M.A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaestiones Mathematicae 32 (2009) 119-129, doi: 10.2989/QM.2009.32.1.10.712. Zbl1168.05348
- [11] V.R. Kulli and S.C. Sigarkanti, Inverse domination in graphs, Nat. Acad. Sci. Lett. 14 (1991) 473-475. Zbl0906.05038
- [12] C. Löwenstein and D. Rautenbach, Pairs of disjoint dominating sets and the minimum degree of graphs, Graphs Combin. 26 (2010) 407-424, doi: 10.1007/s00373-010-0918-9. Zbl1219.05125
- [13] O. Ore, Theory of Graphs, Amer. Math. Soc. Transl. 38 (Amer. Math. Soc., Providence, RI, 1962) 206-212.
- [14] B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989) 7-11. Zbl0688.05066
- [15] B. Zelinka, Domatic numbers of graphs and their variants: A survey, in: Domination in graphs: Advanced topics, T.W. Haynes et al. eds (Marcel Dekker, New York, 1998), 351-377. Zbl0894.05026

## Citations in EuDML Documents

top## NotesEmbed ?

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