Downhill and Uphill Domination in Graphs
Document Type
Article
Publication Date
2-1-2017
Description
Placing degree constraints on the vertices of a path yields the definitions of uphill and downhill paths. Specifically, we say that a path π = v1, v2, ⋯ vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(v1) ≥ deg(vi+1). Conversely, a path π = u1, u2, ⋯ uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(u1) ≤ deg(ui+1). The downhill domination number of a graph G is defined to be 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 explore the properties of these invariants and their relationships with other invariants. We also determine a Vizing-like result for the downhill (respectively, uphill) domination numbers of Cartesian products.
Citation Information
Deering, Jessie; Haynes, Teresa W.; Hedetniemi, Stephen T.; and Jamieson, William. 2017. Downhill and Uphill Domination in Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol.100 27-35. ISSN: 0835-3026