Downhill domination in graphs
Teresa W. Haynes, Stephen T. Hedetniemi, William B. Jamieson, Jessie D. Jamieson · Discussiones Mathematicae Graph Theory · 2014
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.