Downhill domination problem in graphs

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. A downhill dominating set DDS is a set S⊆V having the property that every vertex v∈V lies on a downhill path originating from some vertex in S. The downhill domination numberγdn(G) equals the minimum cardinality of a DDS of G. A DDS having minimum cardinality is called a γdn-set of G. In this note, we give an enumeration of all the distinct γdn-sets of G, and we show that there is a linear time algorithm to determine the downhill domination number of a graph.