Trees with unique minimum total dominating sets

• Autorzy: Teresa W. Haynes , Michael A. Henning
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

domination; total domination

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2002
• Tom: 22
• Numer: 2
• Strony: 233-246

Daty

wydano

2002

otrzymano

2001-02-10

poprawiono

2001-11-06

Twórcy

autor

Teresa W. Haynes

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

autor

Michael A. Henning

• Department of Mathematics, University of Natal, Private Bag X01, Pietermaritzburg, 3209 South Africa

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1172