Downhill domination problem in graphs

作者：Chen Xue gang^*; Fujita Shinya

来源：Information Processing Letters, 2015, 115(6-8): 580-581.

DOI：10.1016/j.ipl.2015.02.003

• Combinatorial problems
• Downhill domination number
• Direct dominating set
• Linear time algorithm

A path pi = (v(1), v(2), ... , v(k+1)) in a graph G = (V, E) is a downhill path if for every i, 1 <= i <= k, deg(v(i)) >= deg(v(i+1)), where deg(v(i)) denotes the degree of vertex v(i) is an element of V. A downhill dominating set DDS is a set S subset of V having the property that every vertex v is an element of V lies on a downhill path originating from some vertex in S. The downhill domination number gamma(dn)(G) equals the minimum cardinality of a DDS of G. A DDS having minimum cardinality is called a gamma(dn)-set of G. In this note, we give an enumeration of all the distinct gamma(dn)-sets of G, and we show that there is a linear time algorithm to determine the downhill domination number of a graph.

• 出版日期2015-8
• 单位华北电力大学（保定）; 北京工业大学; 华北电力大学