Download PDF - Trees with unique minimum total dominating setsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Trees with unique minimum total dominating sets

Authors 1, 2

Affiliations

  1. Department of Mathematics, East Tennessee State University, Johnson City, TN 37614 USA
  2. Department of Mathematics, University of Natal, Private Bag X01, Pietermaritzburg, 3209 South Africa

Abstract

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.

Keywords

ENG
domination, total domination

Bibliography

  1. G. Chartrand and L. Lesniak, Graphs & Digraphs, third edition (Chapman & Hall, London, 1996).
  2. E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304.
  3. E. Cockayne, M.A. Henning and C.M. Mynhardt, Vertices contained in every minimum total dominating set of a tree, to appear in Discrete Math.
  4. O. Favaron, M.A. Henning, C.M. Mynhardt and J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34 (2000) 9-19, doi: 10.1002/(SICI)1097-0118(200005)34:1<9::AID-JGT2>3.0.CO;2-O
  5. G. Gunther, B. Hartnell, L.R. Markus and D. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994) 55-63.
  6. G. Gunther, B. Hartnell and D. Rall, Graphs whose vertex independence number is unaffected by single edge addition or deletion, Discrete Appl. Math. 46 (1993) 167-172, doi: 10.1016/0166-218X(93)90026-K.
  7. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
  8. T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
  9. M.A. Henning, Graphs with large total domination number, J. Graph Theory 35 (2000) 21-45, doi: 10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F
  10. G. Hopkins and W. Staton, Graphs with unique maximum independent sets, Discrete Math. 57 (1985) 245-251, doi: 10.1016/0012-365X(85)90177-3.
Discussiones Mathematicae Graph Theory
2002/22/2
Export to PBN, Opens in new tab
Pages:
233-246
Main language of publication
English
Received
2001-02-10
Accepted
2001-11-06
Published
2002

DOI: 10.7151/dmgt.1172

Exact and natural sciences