Type of Document Master's Thesis Author Plummer, Andrew Robert Author's Email Address aplummer1@student.gsu.edu URN etd-11292006-224238 Title Characterizations in Domination Theory Degree Master of Science Department Mathematics and Statistics Advisory Committee
Advisor Name Title Dr. Johannes H. Hattingh Committee Chair Dr. George Davis Committee Member Dr. Guantao Chen Committee Member Keywords
- Dominating Set
- Nordhaus-Gaddum
- Total Restrained Domination
- Restrained Domination
- Domination
Date of Defense 2006-11-28 Availability unrestricted Abstract Let G = (V,E) be a graph. A set R is a restrained dominating set (total restraineddominating 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.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access plummer_andrew_r_200612_masters.pdf 300.16 Kb 00:01:23 00:00:42 00:00:37 00:00:18 00:00:01