ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


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


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


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 3t-critical graphs G, that is, γt-critical graphs with γt(G) = 3, the diameter of G is either 2 or 3. We characterise the 3t-critical graphs G with diam G = 3.


[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