# Downhill Domination in Graphs

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

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 3, page 603-612
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTeresa W. Haynes, et al. "Downhill Domination in Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 603-612. <http://eudml.org/doc/267807>.

@article{TeresaW2014,

abstract = {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},

author = {Teresa W. Haynes, Stephen T. Hedetniemi, Jessie D. Jamieson, William B. Jamieson},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {downhill path; downhill domination number},

language = {eng},

number = {3},

pages = {603-612},

title = {Downhill Domination in Graphs},

url = {http://eudml.org/doc/267807},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Teresa W. Haynes

AU - Stephen T. Hedetniemi

AU - Jessie D. Jamieson

AU - William B. Jamieson

TI - Downhill Domination in Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 3

SP - 603

EP - 612

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

LA - eng

KW - downhill path; downhill domination number

UR - http://eudml.org/doc/267807

ER -

## References

top- [1] T.W. Haynes, S.T. Hedetniemi, J. Jamieson and W. Jamieson, Downhill and uphill domination in graphs, submitted for publication (2013). Zbl1295.05176
- [2] P. Hall, On representation of subsets, J. London Math. Soc. 10 (1935) 26-30. Zbl0010.34503
- [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998). Zbl0890.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. Zbl1293.05051
- [5] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.