Download PDF - Partitioning a graph into a dominating set, a total dominating set, and something elseAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 2, 2

Affiliations

  1. Department of Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa
  2. Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany

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.

Keywords

ENG
domination, total domination, domatic number, vertex partition, Petersen graph

Bibliography

  1. N.J. Calkin and P. Dankelmann, The domatic number of regular graphs, Ars Combin. 73 (2004) 247-255.
  2. G.S. Domke, J.E. Dunbar and L.R. Markus, The inverse domination number of a graph, Ars Combin. 72 (2004) 149-160.
  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.
  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).
  6. T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in graphs: Advanced topics (Marcel Dekker, New York, 1998).
  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.
  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.
  9. M.A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162.
  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.
  11. V.R. Kulli and S.C. Sigarkanti, Inverse domination in graphs, Nat. Acad. Sci. Lett. 14 (1991) 473-475.
  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.
  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.
  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.
Discussiones Mathematicae Graph Theory
2010/30/4
Export to PBN, Opens in new tab
Pages:
563-574
Main language of publication
English
Received
2009-07-18
Accepted
2009-11-09
Published
2010

DOI: 10.7151/dmgt.1514

Exact and natural sciences