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.

Degree constraints on the vertices of a path allow for the definitions of uphill and downhill paths. Specifically, we say that a path P = vi, v2,⋯ vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(v1+1). Conversely, a path π = u1, u2,⋯ uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(ui) ≤ deg(ui+1). The downhill domination number of a graph G is 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 give a polynomial time algorithm to find a minimum downhill dominating set and a minimum uphill dominating set for any graph.

Placing degree constraints on the vertices of a path yields the definitions of uphill and downhill paths. Specifically, we say that a path π = v1, v2, ⋯ vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(v1) ≥ deg(vi+1). Conversely, a path π = u1, u2, ⋯ uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(u1) ≤ deg(ui+1). 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 explore the properties of these invariants and their relationships with other invariants. We also determine a Vizing-like result for the downhill (respectively, uphill) domination numbers of Cartesian products.