Total Domination Subdivision Numbers of Trees
Document Type
Article
Publication Date
9-28-2004
Description
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 yγ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγ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. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1 ≤sdγt (T)≤3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.
Citation Information
Haynes, Teresa W.; Henning, Michael A.; and Hopkins, Lora. 2004. Total Domination Subdivision Numbers of Trees. Discrete Mathematics. Vol.286(3). 195-202. https://doi.org/10.1016/j.disc.2004.06.004 ISSN: 0012-365X