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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:honors-1111 |
| Date | 01 May 2013 |
| Creators | Jamieson, William |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Undergraduate Honors Theses |
| Rights | Copyright by the authors., http://creativecommons.org/licenses/by-nc-nd/3.0/ |
Page generated in 0.0018 seconds