Bounding the total domination subdivision number of a graph in terms of its order

The total domination subdivision number ${\mathrm{sd}}_{{\gamma }_t}(G)$ of a graph G is 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. In this paper we prove that ${\mathrm{sd}}_{{\gamma }_t}(G)\le \lfloor \frac{2n}{3}\rfloor$ for any simple connected graph G of order n≥3 other than K 4. We also determine all simple connected graphs G with ${\mathrm{sd}}_{{\gamma }_t}(G)=\lfloor \frac{2n}{3}\rfloor$