Downhill domination in graphs

Abstract

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.