Characterization of graphs with orientable total domination number equal to $|V|-1$

Abstract

In a directed graph $D$, a vertex subset $S\subseteq V$ is a total dominating set if every vertex of $D$ has an in-neighbor from $S$. A total dominating set exists if and only if every vertex has at least one in-neighbor. We call the orientation of such directed graphs valid. The total domination number of $D$, denoted by ${\gamma }_t(D)$, is the size of the smallest total dominating set of $D$. For an undirected graph $G$, we investigate the upper (or lower) orientable total domination number of $G$, denoted by ${\mathrm{DOM}}_t(G)$ (or ${\mathrm{dom}}_t(G)$), that is the maximum (or minimum) of the total domination numbers over all valid orientations of $G$. We characterize those graphs for which ${\mathrm{DOM}}_t(G)=|V(G)|-1$, and consequently we show that there exists a family of graphs for which ${\mathrm{DOM}}_t(G)$ and ${\mathrm{dom}}_t(G)$ can be as far as possible, namely ${\mathrm{DOM}}_t(G)=|V(G)|-1$ and ${\mathrm{dom}}_t(G)=3$.