Downhill and Uphill Domination in Graphs

Abstract

Placing degree constraints on the vertices of a path yields the definitions of uphill and downhill paths. Specifically, we say that a path $\pi =v_1,v_2,\dots ,v_{k+1}$ is a downhill path if for every $i$, $1\le i\le k$, $\mathrm{deg}(v_i)\ge \mathrm{deg}(v_{i+1})$. Conversely, a path $\pi =u_1,u_2,\dots ,u_{k+1}$ is an uphill path if for every $i$, $1\le i\le k$, $\mathrm{deg}(u_i)\le \mathrm{deg}(u_{i+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.