$4_t$-Critical Graphs with Maximum Diameter

Abstract

Let ${\gamma }_t(G)$ denote the total domination number of the graph $G$. A graph $G$ is said to be total domination edge critical, or simply ${\gamma }_t$-critical, if ${\gamma }_t(G+e)<{\gamma }_t(G)$ for each edge $e\in E(\overline{G})$. We show that, for $4_t$-critical graphs $G$, that is, ${\gamma }_t$-critical graphs with ${\gamma }_t(G)=4$, the diameter of $G$ is either $2$, $3$, or $4$. Further, we characterize structurally the $4_t$-critical graphs $G$ with $\text{diam}(G)=4$.