DMGT

Discussiones Mathematicae Graph Theory 22(2) (2002) 233-246
DOI: https://doi.org/10.7151/dmgt.1172

TREES WITH UNIQUE MINIMUM TOTAL DOMINATING SETS

Teresa W. Haynes

Department of Mathematics
East Tennessee State University
Johnson City, TN 37614 USA

Michael A. Henning

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: domination, total domination.

2000 Mathematics Subject Classification: 05C069.

References

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

Received 10 February 2001
Revised 6 November 2001