Date of Award

5-2015

Degree Type

Honors College Thesis

Department

Mathematics

First Advisor

Samuel Jeremy Lyle, Ph.D.

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.

Share

COinS