Geodesic
Downhill domination in graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 603-612 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2014},
     volume = {34},
     number = {3},
     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
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
%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/

[1] T.W. Haynes, S.T. Hedetniemi, J. Jamieson and W. Jamieson, Downhill and uphill domination in graphs, submitted for publication (2013).

[2] P. Hall, On representation of subsets, J. London Math. Soc. 10 (1935) 26-30.

[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998).

[4] J.D. Hedetniemi, S.M. Hedetniemi, S.T. Hedetniemi and T. Lewis, Analyzing graphs by degrees, AKCE Int. J. Graphs Comb., to appear.

[5] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962).