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
@article{bwmeta1.element.doi-10_7151_dmgt_1760,
author = {Teresa W. Haynes and Stephen T. Hedetniemi and Jessie D. Jamieson and William B. Jamieson},
title = {Downhill Domination in Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {603-612},
zbl = {1295.05176},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1760}
}
Teresa W. Haynes; Stephen T. Hedetniemi; Jessie D. Jamieson; William B. Jamieson. Downhill Domination in Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 603-612. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1760/
[1] T.W. Haynes, S.T. Hedetniemi, J. Jamieson and W. Jamieson, Downhill and uphill domination in graphs, submitted for publication (2013). | Zbl 1295.05176
[2] P. Hall, On representation of subsets, J. London Math. Soc. 10 (1935) 26-30. | Zbl 0010.34503
[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998). | Zbl 0890.05002
[4] J.D. Hedetniemi, S.M. Hedetniemi, S.T. Hedetniemi and T. Lewis, Analyzing graphs by degrees, AKCE Int. J. Graphs Comb., to appear. | Zbl 1293.05051
[5] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962).