Total domination subdivision numbers of trees. (English) Zbl 1054.05076

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


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees


Zbl 1020.05048
Full Text: DOI


[1] Cockayne, E.J.; Dawes, R.M.; Hedetniemi, S.T., Total domination in graphs, Networks, 10, 211-219, (1980) · Zbl 0447.05039
[2] Haynes, T.W.; Hedetniemi, S.M.; Hedetniemi, S.T., Domination and independence subdivision numbers of graphs, Discuss. math. graph theory, 20, 271-280, (2000) · Zbl 0984.05066
[3] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J., Fundamentals of domination in graphs, (1998), Marcel Dekker New York · Zbl 0890.05002
[4] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998. · Zbl 0883.00011
[5] Haynes, T.W.; Hedetniemi, S.T.; van der Merwe, L.C., Total domination subdivision numbers, J. combin. math. combin. comput., 44, 115-128, (2003) · Zbl 1020.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.