Geodesic
Downhill domination in graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 603-612

Voir la notice de l'article provenant de la source Library of Science

A path π = (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 ∈ 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.
Keywords: downhill path, downhill domination number 
@article{DMGT_2014_34_3_a12,
     author = {Haynes, Teresa W. and Hedetniemi, Stephen T. and Jamieson, Jessie D. and Jamieson, William B.},
     title = {Downhill domination in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {603--612},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a12/}
}
TY  - JOUR
AU  - Haynes, Teresa W.
AU  - Hedetniemi, Stephen T.
AU  - Jamieson, Jessie D.
AU  - Jamieson, William B.
TI  - Downhill domination in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 603
EP  - 612
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a12/
LA  - en
ID  - DMGT_2014_34_3_a12
ER  - 
%0 Journal Article
%A Haynes, Teresa W.
%A Hedetniemi, Stephen T.
%A Jamieson, Jessie D.
%A Jamieson, William B.
%T Downhill domination in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 603-612
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a12/
%G en
%F DMGT_2014_34_3_a12
Haynes, Teresa W.; Hedetniemi, Stephen T.; Jamieson, Jessie D.; Jamieson, William B. Downhill domination in graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 603-612. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a12/