A Polynomial Time Algorithm for Downhill and Uphill Domination

作者：Deering Jessie; Haynes Teresa W^*; Hedetniemi Stephen T; Jamieson William

来源：Utilitas Mathematica, 2017, 104: 23-30.

• downhill path
• uphill path
• downhill domination number
• uphill domination number
• algorithm

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(1), v(2), ... v(k+1) is a downhill path if for every i, 1 <= i <= k, deg(v(i)) >= deg(v(i+1)). Conversely, a path pi = u(1), u(2),...u(k+1) is an uphill path if for every i, 1 <= i <= k, deg(u(i)) <= 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.

• 出版日期2017-9