Portal de Periódicos da CAPES

Downhill domination in graphs

2014; De Gruyter Open; Volume: 34; Issue: 3 Linguagem: Inglês

10.7151/dmgt.1760

2083-5892

Teresa W. Haynes, Stephen T. Hedetniemi, William B. Jamieson, Jessie D. Jamieson,

Graph Labeling and Dimension Problems

The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds.In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order.We characterize the graphs obtaining each of these bounds.