A polynomial time algorithm for downhill and uphill domination

Abstract

Degree constraints on the vertices of a path allow for the definitions of uphill and downhill paths. Specifically, we say that a path P = v_i, v₂,⋯ v_k+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(v₁₊₁). Conversely, a path π = u₁, u₂,⋯ u_k+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(ui) ≤ deg(u_i+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.