Orientable total domination in graphs

Abstract

Given a directed graph $D$, a set $S\subseteq V(D)$ is a total dominating set of $D$ if each vertex in $D$ has an in-neighbor in $S$. The total domination number of $D$, denoted ${\gamma }_t(D)$, is the minimum cardinality among all total dominating sets of $D$. Given an undirected graph $G$, we study the maximum and minimum total domination numbers among all orientations of $G$. That is, we study the upper (or lower) orientable domination number of $G$, ${\mathrm{DOM}}_{\mathrm{t}}(\mathrm{G})$ (or ${\mathrm{dom}}_{\mathrm{t}}(\mathrm{G})$), which is the largest (or smallest) total domination number over all orientations of $G$. We characterize those graphs with ${\mathrm{DOM}}_{\mathrm{t}}(\mathrm{G})={\mathrm{dom}}_{\mathrm{t}}(\mathrm{G})$ when the girth is at least $7$ as well as those graphs with ${\mathrm{dom}}_{\mathrm{t}}(\mathrm{G})=|V(\mathrm{G})|-1$. We also consider how these parameters are effected by removing a vertex from $G$, give exact values of ${\mathrm{DOM}}_{\mathrm{t}}({\mathrm{K}}_{\mathrm{m},\mathrm{n}})$ and ${\mathrm{dom}}_{\mathrm{t}}({\mathrm{K}}_{\mathrm{m},\mathrm{n}})$ and bound these parameters when $G$ is a grid graph.