PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 187-205
DOI: https://doi.org/10.7151/dmgt.1143

TOTAL DOMINATION EDGE CRITICAL GRAPHS WITH MAXIMUM DIAMETER

Lucas C. van der Merwe, Cristine M. Mynhardt University of South Africa Pretoria, South Africa

Teresa W. Haynes East Tennessee State University Johnson City, TN 37614 USA

Abstract

Denote the total domination number of a graph G by γ_t(G). A graph G is said to be total domination edge critical, or simply γ_t-critical, if γ_t(G+e) < γ_t(G) for each edge e ∈ E([`G]). For 3_t-critical graphs G, that is, γ_t-critical graphs with γ_t(G) = 3, the diameter of G is either 2 or 3. We characterise the 3_t-critical graphs G with diam G = 3.

References

[1]	E. Cockayne, R. Dawes and S. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304.
[2]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
[3]	T.W. Haynes, C.M. Mynhardt and L.C. van der Merwe, Total domination edge critical graphs, Utilitas Math. 54 (1998) 229-240.
[4]	T.W. Haynes, C.M. Mynhardt and L.C. van der Merwe, Criticality index of total domination, Congr. Numer. 131 (1998) 67-73.
[5]	D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory (B) 34 (1983) 65-76, doi: 10.1016/0095-8956(83)90007-2.
[6]	D.P. Sumner and E. Wojcicka, Graphs critical with respect to the domination number, Domination in Graphs: Advanced Topics (Chapter 16), T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds. (Marcel Dekker, Inc., New York, 1998).

Received 5 October 2000