A Polynomial Time Algorithm for Downhill and Uphill Domination
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.
Deering, Jessie; Haynes, Teresa W.; Hedetniemi, Stephen T.; and Jamieson, William. 2017. A Polynomial Time Algorithm for Downhill and Uphill Domination. Utilitas Mathematica. Vol.104 23-30. ISSN: 0315-3681