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 viV. The downhill domination number equals the minimum cardinality of a set S ⊂ V having the property that every vertex vV 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

Copyright

Copyright by the authors.

Included in

Mathematics Commons

Share

COinS