Total domination subdivision numbers. (English) Zbl 1020.05048

Haynes, Teresa W.; Hedetniemi, Stephen T.; van der Merwe, Lucas C.

J. Comb. Math. Comb. Comput. 44, 115-128 (2003).

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\).

Reviewer: Dieter Rautenbach (Aachen)

MSC:

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