Honors Program
Honors in Mathematics
Date of Award
5-2013
Thesis Professor(s)
Teresa Haynes
Thesis Professor Department
Mathematics and Statistics
Thesis Reader(s)
Debra Knisley, Donald Luttermoser
Abstract
A path π = (v1, v2,...vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 < i < k, deg(vi) > deg(vi+1), where deg(vi) denotes the degree of vertex vi ∊ V. The downhill domination number equals the minimum cardinality of a set S ⊂ V having the property that every vertex v ∊ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds.
Document Type
Honors Thesis - Withheld
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Recommended Citation
Jamieson, William, "General Bounds on the Downhill Domination Number in Graphs." (2013). Undergraduate Honors Theses. Paper 107. https://dc.etsu.edu/honors/107
Copyright
Copyright by the authors.