Total domination subdivision numbers of trees (Q1887637)

The total domination subdivision number \(\text{ sd}_{\gamma_t}(G)\) of a graph \(G\) is the minimum number of edges whose subdivision increases the total domination number \({\gamma_t}(G)\) of \(G\). \textit{T. W. Haynes} et al. [J. Comb. Math. Comb. Comput. 44, 115--128 (2003; Zbl 1020.05048)] have shown that \(1\leq \text{ sd}_{\gamma_t}(T)\leq 3\) for any tree \(T\). In the present paper the authors provide a constructive characterization of the family \({\mathcal F}\) of trees \(T\) with \(\text{ sd}_{\gamma_t}(T)=3\). The family \({\mathcal F}\) consists of labeled trees, contains a path of order \(6\) whose vertices have labels \(c,b,a,a,b,c\) and is closed under the two operations \({\mathcal T}_1\) and \({\mathcal T}_2\) where \({\mathcal T}_1\) consists of adding a path of order \(3\) labeled \(a,b,c\) to a tree \(T\in {\mathcal F}\) and joining the vertex labeled \(a\) to a vertex labeled \(a\) in \(T\) and \({\mathcal T}_2\) consists of adding a path of order \(4\) labeled \(a,a,b,c\) to a tree \(T\in {\mathcal F}\) and joining the endvertex labeled \(a\) to a vertex labeled \(b\) or \(c\) in \(T\).