Degree constraints on the vertices of a path allow for the definitions of uphill and downhill paths. Specifically, we say that a path P = vi, v2,⋯ vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(v1+1). Conversely, a path π = u1, u2,⋯ uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(ui) ≤ deg(ui+1). The downhill domination number of a graph G is the minimum cardinality of a set S of vertices such that every vertex in V lies on a downhill path from some vertex in S. The uphill domination number is defined as expected. We give a polynomial time algorithm to find a minimum downhill dominating set and a minimum uphill dominating set for any graph.
Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-11836 |
Date | 01 September 2017 |
Creators | Deering, Jessie, Haynes, Teresa W., Hedetniemi, Stephen T., Jamieson, William |
Publisher | Digital Commons @ East Tennessee State University |
Source Sets | East Tennessee State University |
Detected Language | English |
Type | text |
Source | ETSU Faculty Works |
Page generated in 0.0014 seconds