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

Abstract

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

How to cite

top

Michael 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. [1] N.J. Calkin and P. Dankelmann, The domatic number of regular graphs, Ars Combin. 73 (2004) 247-255. Zbl1073.05046
  2. [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. [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. [4] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001). 
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  6. [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. [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. [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. [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. [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. [11] V.R. Kulli and S.C. Sigarkanti, Inverse domination in graphs, Nat. Acad. Sci. Lett. 14 (1991) 473-475. Zbl0906.05038
  12. [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. [13] O. Ore, Theory of Graphs, Amer. Math. Soc. Transl. 38 (Amer. Math. Soc., Providence, RI, 1962) 206-212. 
  14. [14] B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989) 7-11. Zbl0688.05066
  15. [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

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.