Honors Program
Honors in Mathematics
Date of Award
5-2013
Thesis Professor(s)
Teresa Haynes
Thesis Professor Department
Mathematics and Statistics
Thesis Reader(s)
Robert Gardner, Richard Ignace
Abstract
Placing degree constraints on the vertices of a path allows the definitions of uphill and downhill paths. Specifically, we say that a path π = v1, v2,...vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1). Conversely, a path π = u1, u2,...uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(ui) ≤ deg(ui+1). We investigate graphical parameters related to downhill and uphill paths in graphs. For example, a downhill path set is a set P of vertex disjoint downhill paths such that every vertex v ∈ V belongs to at least one path in P, and the downhill path number is the minimum cardinality of a downhill path set of G. For another example, the downhill domination number of a graph G is defined to be the minimum cardinality of a set S of vertices such that every vertex in V lies on a downhill path from some vertex in S. The uphill domination number is defined as expected. We determine relationships among these invariants and other graphical parameters related to downhill and uphill paths. We also give a polynomial time algorithm to find a minimum downhill dominating set and a minimum uphill dominating set for any graph.
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
Deering, Jessie, "Uphill & Downhill Domination in Graphs and Related Graph Parameters." (2013). Undergraduate Honors Theses. Paper 103. https://dc.etsu.edu/honors/103
Copyright
Copyright by the authors.