Date of Award
Spring 5-2015
Degree Type
Honors College Thesis
Department
Mathematics
First Advisor
Samuel Jeremy Lyle
Advisor Department
Mathematics
Abstract
Using information provided by Ryan Pepper and Ermelinda DeLaVina in their paper On the 2-Domination number and Annihilation Number, I developed a new bound on the 2- domination number of trees. An original bound, γ2(G) ≤ (n+n1)/ 2 , had been shown by many other authors. Our goal was to generate a tighter bound in some cases and work towards generating a more general bound on the 2-domination number for all graphs. Throughout the span of this project I generated and proved the bound γ2(T ) ≤ 1/3 (n + 2n1 + n2). To prove this bound I first proved that the 2-domination number of a tree was less than or equal to the sum of two sub-trees formed by the deletion of an edge: γ2(T ) ≤ γ2(T1) + γ2(T2). From there, I proved our bound by showing that a minimum counter-example did not exist. A large portion of the results involves cases where a graph T is considered the minimum counter-example for the sake of contradiction. From there, I showed that if T was a counter-example, then a sub-tree T1 was also a counter-example, meaning that T would no longer be the minimum counter-example. The last portion of the results is a section comparing the two bounds on the 2-domination number with respect to the number of edges and the degrees of those edges.
Copyright
Copyright for this thesis is owned by the author. It may be freely accessed by all users. However, any reuse or reproduction not covered by the exceptions of the Fair Use or Educational Use clauses of U.S. Copyright Law or without permission of the copyright holder may be a violation of federal law. Contact the administrator if you have additional questions.
Recommended Citation
Patterson, Sean C., "2-Domination and Annihilation Numbers" (2015). Honors Theses. 279.
https://aquila.usm.edu/honors_theses/279