Total domination subdivision numbers. (English) Zbl 1020.05048

The authors introduce and study the total domination subdivision number \(sd_{\gamma_t}(G)\) of a graph \(G\) as the minimum number of edges that must be subdivided (where each edge of \(G\) can be subdivided at most once) in order to increase the total domination number. The analogous concept has been introduced by Arumugam in 2000 for the ordinary domination number. They establish upper bounds on \(sd_{\gamma_t}\) and determine it for several special graphs. Furthermore, they give several conditions which imply \(sd_{\gamma_t}(G)\leq 3\) and characterize the caterpillars \(T\) with \(sd_{\gamma_t}(T)=3\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory