Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Downhill Domination in Graphs

100%

Haynes T. W., Hedetniemi S. T., Jamieson J. D., Jamieson W. B.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 3

603-612

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. 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

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Haynes T. W.

1 Hedetniemi S. T.

1 Jamieson J. D.

1 Jamieson W. B.

1 2014

Wyniki wyszukiwania

Downhill Domination in Graphs