| In graph theory, domination in graphs has been studied extensively. In contrast, there has been relatively little research involving domination in digraphs. In a digraph D, a vertex v openly (or 1-step) out-dominates every vertex to which v is adjacent and openly in-dominates every vertex from which v is adjacent. More generally, a vertex v k-step out-dominates every vertex w such that {dollar}d(v, w)=k{dollar} and k-step in-dominates every vertex u such that {dollar}d(u, v)=k{dollar}. A set S of vertices of D is a k-step out-dominating set if every vertex of D is k-step out-dominated by some vertex of S, and the minimum cardinality of a k-step out-dominating set is the k-step out-domination number {dollar}psbsp{lcub}k{rcub}{lcub}+{rcub}(D){dollar}. Similar definitions are made for a k-step in-dominating set and the k-step in-domination number {dollar}psbsp{lcub}k{rcub}{lcub}-{rcub}(D){dollar}. A set S of vertices of D is a k-step twin dominating set of D if every vertex of D is k-step in-dominated by some vertex of S and is k-step out-dominated by some vertex of S. The k-step twin domination number {dollar}psbsp{lcub}k{rcub}{lcub}*{rcub}(D){dollar} of D is defined in the expected manner.; We determine the values of these parameters for various digraphs. We also study the minimum and maximum of the k-step twin domination numbers, where the minimum and maximum is taken over all possible orientations of a graph. Furthermore, bounds on these parameters are determined and some Nordhaus-Gaddum-type results are presented. |
