The domination subdivision number of a graph is the minimum number of edges that must be subdivided in order to increase the domination number of the graph. Likewise, the total domination subdivision number is the minimum number of edges that must be subdivided in order to increase the total domination number. First, this thesis provides a complete survey of established bounds on the domination subdivision number and the total domination subdivision number. Then in Chapter 4, new results regarding bounds on the total domination subdivision number are given. Finally, a characterization of the total domination subdivision number of caterpillars is presented in Chapter 5.

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.

A set S of vertices of a graph G = (V, E) is a dominating set if every vertex in V - S is adjacent to some vertex in 3. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. In June 2000, Arumugam conjectured that 1 ≤ sdγ(G) ≤ 3 for any graph G. However, a counterexample to this conjecture given in [6] suggests the modified conjecture that 1 ≤ sdγ(G) ≤ 4 for any graph G. It is also conjectured in [6] that for every graph G with minimum degree δ(G) ≥ 2, sdγ(G) ≤ δ(G) + 1. In this paper we extend several previous results and consider evidence in support of these two conjectures.