On total domination subdivision numbers of trees

Abstract

A set $S$ of vertices in a graph $G$ is a total dominating set of $G$ if every vertex is adjacent to a vertex in $S$. The total domination number ${\gamma }_t(G)$ is the minimum cardinality of a total dominating set of $G$. The total domination subdivision number $\mbox{sd}_{γ_t}(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the total domination number. Haynes et al. (Discrete Math. 286 (2004) 195--202) have given a constructive characterization of trees whose total domination subdivision number is~$3$. In this paper, we give new characterizations of trees whose total domination subdivision number is 3.

15 pages, 7 figures