Downhill domination problem in graphs
2015; Elsevier BV; Volume: 115; Issue: 6-8 Linguagem: Inglês
10.1016/j.ipl.2015.02.003
ISSN1872-6119
Autores Tópico(s)Limits and Structures in Graph Theory
ResumoA 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.
Referência(s)