## 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 π = v_{1}, v_{2},...v_{k+1} is a *downhill path* if for every *i*, 1 ≤ *i* ≤ *k*, deg(*v _{i}*) ≥ deg(

*v*). Conversely, a path π =

_{i+1}*u*is an

_{1}, u_{2},...u_{k+1}*uphill path*if for every

*i*, 1 ≤

*i*≤

*k*, deg(

*u*) ≤ deg(

_{i}*u*). 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

_{i+1}*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.