Date of Award
Master of Science (MS)
Mathematics and Statistics
Dr. Johannes H. Hattingh - Chair
Dr. Guantao Chen
Dr. George Davis
Let G = (V,E) be a graph. A set R is a restrained dominating set (total restrained dominating set, resp.) if every vertex in V − R (V) is adjacent to a vertex in R and (every vertex in V −R) to a vertex in V −R. The restrained domination number of G (total restrained domination number of G), denoted by gamma_r(G) (gamma_tr(G)), is the smallest cardinality of a restrained dominating set (total restrained dominating set) of G. If T is a tree of order n, then gamma_r(T) is greater than or equal to (n+2)/3. We show that gamma_tr(T) is greater than or equal to (n+2)/2. Moreover, we show that if n is congruent to 0 mod 4, then gamma_tr(T) is greater than or equal to (n+2)/2 + 1. We then constructively characterize the extremal trees achieving these lower bounds. Finally, if G is a graph of order n greater than or equal to 2, such that both G and G' are not isomorphic to P_3, then gamma_r(G) + gamma_r(G') is greater than or equal to 4 and less than or equal to n +2. We provide a similar result for total restrained domination and characterize the extremal graphs G of order n achieving these bounds.
Plummer, Andrew Robert, "Characterizations in Domination Theory" (2006). Mathematics Theses. Paper 19.