Name
Abstract | ||
|---|---|---|
A path pi = (v(1), v(2), . . . , Vk+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) is an element of V. The downhill domination number equals the minimum cardinality of a set S subset of V having the property that every vertex v is an element of 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.7151/dmgt.1760 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
downhill path,downhill domination number | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Cardinality,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
34 | 3 | 1234-3099 |
Citations | PageRank | References |
1 | 0.43 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Teresa W. Haynes | 1 | 774 | 94.22 |
| Stephen T. Hedetniemi | 2 | 1575 | 289.01 |
| William B. Jamieson | 3 | 1 | 0.43 |
| Jessie D. Jamieson | 4 | 1 | 0.43 |