Article in press
Authors:
Title:
On total domination subdivision numbers of trees
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-05-26 , Revised: 2025-05-07 , Accepted: 2025-05-07 , Available online: 2025-05-21 , https://doi.org/10.7151/dmgt.2586
Abstract:
A set $S$ of vertices in a graph $G$ is a total dominating set
of $G$ if every vertex is adjacent to a vertex in $S$. The total domination
number $\gamma_t(G)$ is the minimum cardinality of a total dominating set of $G$.
The total domination subdivision number $\mbox{sd}_{\gamma_t}(G)$ of a graph $G$
is the minimum number of edges that must be subdivided (where each edge in $G$
can be subdivided at most once) in order to increase the total domination
number. Haynes et al. [Total domination subdivision numbers of trees,
Discrete Math. 286 (2004) 195–202] have given a constructive characterization
of trees whose total domination subdivision number is $3$. In this paper, we give
new characterizations of trees whose total domination subdivision number is 3.
Keywords:
trees, total domination number, total domination subdivision number
References:
- T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Structures of Domination in Graphs, Dev. Math. 66 (Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5 - T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003) 115–128.
- T.W. Haynes, M.A. Henning and L. Hopkins, Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory 24 (2004) 457–467.
https://doi.org/10.7151/dmgt.1244 - T.W. Haynes, M.A. Henning and L. Hopkins, Total domination subdivision numbers of trees, Discrete Math. 286 (2004) 195–202.
https://doi.org/10.1016/j.disc.2004.06.004 - M.A. Henning and A. Yeo, Total Domination in Graphs, Springer Monogr. Math. (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6
Close