Total Domination Subdivision Numbers

Abstract

A set $S$ of vertices of a graph $G=(V,E)$ is a total dominating set if every vertex of $V(G)$ is adjacent to some vertex in $S$. The total domination number ${\gamma }_t(G)$ is the minimum cardinality of a total dominating set of $G$. We define the total domination subdivision number $s{d}_{\gamma t}(G)$ to be the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the total domination number. We give upper bounds on the total domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on $G$ sufficient to imply that $s{d}_{\gamma t}(G)\le 3$. On the other hand, we show that this constant upper bound does not hold for all graphs. Finally, we show that $1\le s{d}_{\gamma t}(T)\le 3$ for any tree $T$, and characterize the caterpillars $T$ for which $s{d}_{\gamma t}(T)=3$.