On the k-domination number of digraphs

Abstract

Let $k\ge 1$ be an integer and let D be a digraph with vertex set V(D). A subset $S\subseteq V(D)$ is called a k-dominating set if every vertex not in S has at least k predecessors in S. The k-domination number $\gamma _{k}(D)$ of D is the minimum cardinality of a k-dominating set in D. We know that for any digraph D of order n, $\gamma _{k}(D)\le n$. Obviously the upper bound n is sharp for a digraph with maximum in-degree at most $k-1$. In this paper we present some lower and upper bounds on $\gamma _{k}(D)$. Also, we characterize digraphs achieving these bounds. The special case $k=1$ mostly leads to well known classical results.

1 Introduction

Let $D=(V,A)$ be a digraph (or a directed graph) of order $n=\left| V\right|$, with vertex set V and a set $A\subseteq V\times V$ of directed edges, called arcs. If (x, y) is an arc of D, then the arc (x, y) is oriented from x to y,  x is adjacent to y and y is adjacent from x. We also say x is an in-neighbor (or a predecessor) of y and y is an out-neighbor (or a successor) of x,  and the arc (x, y) is incident to y and incident from x. An arc (x, y) in A is called a symmetrical (an asymmetrical, respectively) arc if (y, x) is in A, ( is not in A, respectively). If for every pair x and y of distinct vertices of D, (x, y) and (y, x) are in A, then D is called a symmetric digraph. And if at most one of (x, y) and (y, x) is in A, then D is called an asymmetric digraph or an oriented graph. The digraphs considered here are finite and simple (with no loops or multiple arcs).

Given a digraph $D=(V,A).$ Let v be a vertex of D. The out-neighborhood of v is the set $N_{D}^{+}(v)=\{u\in V:(v,u)\in A\}$ and the in-neighborhood of v is the set $N_{D}^{-}(v)=\{w\in V:(w,v)\in A\}$. The out-degree of v in D is defined as $d_{D}^{+}(v)=|N_{D}^{+}(v)|$. The maximum out-degree of D is given by $\Delta ^{+}\left( D\right) =\max \left\{ d_{D}^{+}(v):v\in V\right\}$ and the minimum out-degree, $\delta ^{+}\left( D\right) =\min \left\{ d_{D}^{+}(v):v\in V\right\}$. Similarly, the in-degree of v is $d_{D}^{-}(v)=|N_{D}^{-}(v)|$, the maximum in-degree of D is $\Delta ^{-}\left( D\right) =\max \left\{ d_{D}^{-}(v):v\in V\right\}$, the minimum in-degree of D is $\delta ^{-}\left( D\right) =\min \left\{ d_{D}^{-}(v):v\in V\right\}$. For an integer $r>0$, if for every vertex $v\in V$, $d_{D}^{+}(v)=r$ ($d_{D}^{-}(v)=r$, respectively), then D is called r-out-regular (r-in-regular, respectively) digraph. If v is an in-neighbor of each vertex of S,  then we use the notation $v\Longrightarrow S$. For $U\subseteq V$, the subdigraphH of D induced by U, denoted by $H=\left\langle U\right\rangle$ is a digraph $H=\left( U,B\right)$ where $B=\{(x,y)\in A:x,y\in U\}$. If $U=V$ and $B\subset A$, then H is said to be spanning $digraph$ of D.

From a simple graph $G=(V,E)$ we can obtain a digraph $D=(V,E)$ by assigning a direction (possibly both) to each edge of G. We say that D is an orientation of G. Also, we can obtain the undirected graphG from D by replacing each arc (u, v) or symmetrical arc (u, v), (v, u) of D by the edge uv. We say that G is the underlying$graph$ (or the associatedgraph ) of D.

A digraph is connected if its underlying graph is connected. A complete digraph of order n, is a digraph in which its underlying graph is the complete graph $K_{n}$. A tournament of order n denoted by $T_{n}$, is a complete oriented graph. A circuit of order 3, denoted by $C_{3}$, is a tournament $T_{3}$ of order 3 which its vertices $v_{1},v_{2}$ and $v_{3}$ can be (uniquely) ordered, i.e., $(v_{1},v_{2}),(v_{2} ,v_{3}),(v_{3},v_{1})\in A$. For all the definitions not given here we refer the reader to the book of Bang and Gutin (2008).

A subset $S\subseteq$V is a dominating set in a directed graph $D=(V,A)$ if for every vertex $v\in V-S$ there exists a vertex $u\in S$ for which $(u,v)\in A$. The minimum cardinality of a dominating set in D is called the domination number of D, denoted by $\gamma (D)$. A $\gamma \left( D\right)$-set is a dominating set of D with cardinality $\gamma \left( D\right)$. Also, a subset $S\subseteq$V is called an independent set if $\Delta ^{+}\left( \left\langle S\right\rangle \right) =0$. An independent set is maximal if there is no independent set which contains it. The independence number, $\alpha \left( D\right)$, equal the maximum cardinality of a maximal independent set in D. A $\alpha \left( D\right)$-set is an independent set of D with cardinality $\alpha \left( D\right)$.

This is well known to those who study kernels and solutions in digraphs, which are defined as follows. A subset $S\subseteq V$ in a digraph $D=(V,A)$ is called an absorbing set if from every vertex $v\in V-S$ there is a vertex $u\in S$ such that $(v,u)\in A$. That is, S is a dominating set in the directional dual $D^{*}=(V,A^{*})$, where $A^{*}=\{(u,v):(v,u)\in A\}$. A subset $S\subseteq V$ is a kernel of D if S is independent and absorbent and S is a solution of D if S is independent and dominant.

The theory of domination in graphs was formally introduced by Berge (1962) and Ore (1962). Lee (1994) introduced in his doctoral thesis the concept of domination in digraphs, which is a generalization of the concept of domination in graphs where a graph can be seen as an underlying graph (undirected graph) of a symmetric digraph. Domination in undirected graphs has been studied extensively and much more than directed graphs, about 90% of articles on domination only took into account undirected graphs. On the other hand, and for various reasons, there has been relatively little research involving the domination in digraphs. The basic reason is that undirected graphs form a special class of directed graphs (symmetric digraphs). Another raison is that in an undirected graph G, any maximal independent set is also a dominant set, and therefore $\gamma \left( G\right) \le \alpha \left( G\right)$. However, these inequality is not always true for digraphs, and as we can see from circuit $C_{3}$; $\gamma \left( C_{3}\right) =2>1=\alpha \left( C_{3}\right) .$ So a set S is an independent dominating (solution) set in a digraph D if and only if it is a kernel in the dual digraph $D^{*}$. The decision problem of the existence of a solution and kernel in a digraph are known to be NP-complete, see Fraenkel (1981) and Garey and Johnson (1979). For more details, on the domination in graphs and digraphs, see the two excellent books Haynes et al. (1998a) and Haynes et al. (1998b).

Fink and Jacobson (1985a, b) gave another type of generalization of the concept of domination in graphs. In their paper they defined the concept of k-domination in graphs as follows. Given a positive integer k,  a subset $S\subseteq V(G)$ is a k-dominating set for a graph G if every vertex not in S is adjacent to at least k vertices in S. The minimum cardinality of a k-dominating set of G is the k-domination number of G, denoted $\gamma _{k}(G)$. When $k=1$ the 1-domination is the classical domination, $\gamma _{1}(G)=\gamma (G)$. Note that computing the k-domination number in undirected graphs is NP-hard (Jacobson and Peters 1989), and as such, many researchers have sought computationally efficient upper and lower bounds for this parameter. Like domination, k-domination has also been extensively studied; for results on k-domination, we refer the reader to survey given by Chellali et al. (2012).

Ramoul and Blidia (2017) transferred the concept of k-domination in undirected graphs to the k-out-domination in digraphs. In their paper they gave the definition of k-out-domination in digraphs as follows. For a digraph $D=(V,A)$ and k positive integer, a subset S of vertices in a digraph D is called an k-out-dominating set if $\left| N^{+}\left( u\right) \cap S\right| \ge k$, for every vertex u in $V-S$. And they used this definition to define the k-kernel concept.

In our paper, we define another extension of k-domination in graphs given by Fink and Jacobson (1985a, b), which we call it the k-in-domination or simply the k-domination in digraphs defined as follows. A subset S of vertices in a digraph $D=(V$, A) is a k-dominating set if $\left| N^{-}(u)\cap S\right| \ge k$ for every vertex u in $V-S$. The k-domination number of D, denoted by $\gamma _{k}(D)$, is the minimum cardinality of a k-dominating set in D. A $\gamma _{k}\left( D\right)$-set is a k-dominating set of D with cardinality $\gamma _{k}(D)$. This new concept is also an extension of the concept of domination in digraph given by Lee (1994).

In this paper we present some lower and upper bounds for $\gamma _{k}(D)$. Also, we characterize digraphs achieving these bounds. The special case $k=1$ mostly leads to well known classical results.

2 Lower bounds for $\gamma _{k}$ and extremal digraphs

For $k\in {\mathbb {N}} ^{*}$, clearly if D is a digraph with $\Delta ^{-}\left( D\right) \ge k$, then $\gamma _{k}(D)\ge k$. We begin this section by given a characterization of digraphs D satisfying $\gamma _{k}(D)=k$. We denote by $\overrightarrow{K}_{p,q}$ the complete bipartite oriented graph with a bipartition X and Y such that $\left| X\right| =p$, $\left| Y\right| =q$ and $d_{\overrightarrow{K}_{p,q}}^{-}\left( y\right) =p,$$\forall$$y\in Y$.

Proposition 1

Let $D=(V,A)$ be a digraph of order n, k a positive integer and $\Delta ^{-}\left( D\right) \ge k$. Then, $\gamma _{k}(D)=k$ if and only if D contains $\overrightarrow{K}_{k,n-k}$ as a spanning digraph.

Proof

Necessity. Assume that $\gamma _{k}(D)=k$ and let S be a $\gamma _{k}\left( D\right)$-set of D, so every vertex of $V-S$ has exactly k in-neighbors in S. Let $A[S,V-S]=\{\left( u,v\right) \in A:u\in S$ and $v\in V-S\}$, it is clear that the spanning digraph $(S,V-S,A[S,V-S])$ is a complete bipartite oriented graph with a bipartition S and $V-S$ and $\left| S\right| =k$, $\left| V-S\right| =n-k$.

Sufficiency. If D contains $\overrightarrow{K}_{k,n-k}$ as a spanning digraph, then $\overrightarrow{K}_{k,n-k}$ has a bipartition X and Y such that $\left| X\right| =k$, $\left| Y\right| =n-k$ and $d_{\overrightarrow{K}_{k,n-k}}^{-}\left( y\right) =k$ for every $y\in Y$. So X is a k-dominating set. Moreover, $\gamma _{k}(D)\le \gamma _{k}(\overrightarrow{K}_{k,n-k})\le \left| X\right| \le k$, and since $\gamma _{k}(D)\ge k$, we obtain $\gamma _{k}(D)=k$. $\square$

Fink and Jacobson (1985a) gave in their paper a lower bound on the domination number of a graph, $\gamma (G)\ge \dfrac{n}{\Delta \left( G\right) +1}$. The same authors in Fink and Jacobson (1985b), generalized this bound to $\gamma _{k}(G)\ge \dfrac{kn}{\Delta \left( G\right) +k},$ where k a positive integer with $\Delta \ge k$. Ghoshal et al. (1998) extended this bound in digraphs, $\gamma (D)\ge \dfrac{n}{\Delta ^{+}\left( D\right) +1}$. In this section, we give a lower bound for $\gamma _{k}(D)$ in term of n, k and $\Delta ^{+}\left( D\right)$, which is a natural extension for these two lower bounds given above. We also give a characterization of digraphs attaining this bound, which improve the previous bound, when $\Delta ^{+}\left( D\right) <n-k$.

Theorem 2

Let D be a digraph on n vertices with maximum out-degree $\Delta ^{+}\left( D\right) \ge k$, where k is a positive integer. Then

$$\begin{aligned} \gamma _{k}(D)\ge \dfrac{kn}{\Delta ^{+}\left( D\right) +k}\text {,} \end{aligned}$$

with equality if and only if $V=X\cup Y$, where X is independent, each vertex of X has out-degree $\Delta ^{+}\left( D\right)$ and each vertex of Y has exactly k in-neighbors in X.

Proof

Let k be a positive integer. We first prove the lower bound. Let S be a $\gamma _{k}(D)$-set. The number $m(S,V-S)$ of arcs from S to $V-S$ satisfies $k\left| V-S\right| \le m(S,V-S)\le \Delta ^{+}\left| S\right|$. Therefore $\gamma _{k}(D)=\left| S\right| \ge \dfrac{kn}{k+\Delta ^{+}\left( D\right) }$.

Now assume that $\gamma _{k}(D)=\dfrac{kn}{k+\Delta ^{+}\left( D\right) }$. Then we have equality throughout the previous inequality chain. It is clear that each vertex in S has $\Delta ^{+}\left( D\right)$ out-neighbors in $V-S$, and so the set S is independent and each vertex of $V-S$ has exactly k in-neighbors in S.

Conversely, clearly, if D is one of the digraphs described above, then each vertex of X has exactly $\Delta ^{+}\left( D\right)$ out-neighbors in Y and each vertex of Y has exactly k in-neighbors in X. Thus X is a k-dominating set of D and $\left| V-X\right| k=\left| Y\right| k=m(X,Y)=\Delta ^{+}\left( D\right) \left| X\right|$, and so $\gamma _{k}(G)\le \left| X\right| =\dfrac{kn}{k+\Delta ^{+}\left( D\right) }$. Equality holds from the fact that $\gamma _{k} (G)\ge \dfrac{kn}{k+\Delta ^{+}\left( D\right) }$. $\square$

For $k=\Delta ^{-}\left( D\right)$, we have the following.

Corollary 1

Let D be a digraph on n vertices with maximum out-degree $\Delta ^{+}\left( D\right)$ and maximum in-degree $\Delta ^{-}\left( D\right)$. Then $\gamma _{\Delta ^{-}}(D)=\dfrac{\Delta ^{-}\left( D\right) n}{\Delta ^{-}\left( D\right) +\Delta ^{+}\left( D\right) }$ if and only if D is a bipartite digraph with partite sets X and Y, such that every vertex of X has out-degree $\Delta ^{+}\left( D\right)$ and every vertex of Y has in-degree $\Delta ^{-}\left( D\right)$.

3 Upper bounds for $\gamma _{k}$ and extremal digraphs

Let D be a digraph, and let k be a positive integer. It is clear that for any digraph D, $\gamma _{k}(D)\le \gamma _{k+1}(D)$ and $\gamma _{k}(D)\le n$ with equality if and only if $\Delta ^{-}\left( D\right) \le k-1$. Hence, if D is a digraph with maximum in-degree $\Delta ^{-}\left( D\right) \ge k$, then $\gamma _{k}(D)\le n-1$. We begin this section by these tow observations which are useful for the next.

Observation 3

Let k be a positive integer, and let $T_{n}=\left( V,A\right)$ be a k-in-regular tournament of order n. Then $n=2k+1$.

Proof

Let $T_{n}=\left( V,A\right)$ be a k-in-regular tournament of order n. Then, $kn=\left| A\right| =\sum \nolimits _{v\in V}d_{T_{n}}^{-}\left( v\right) =\dfrac{n\left( n-1\right) }{2},$ which implies that $n=2k+1$. $\square$

Observation 4

Let k be a positive integer, and let $T_{n}=\left( V,A\right)$ be a k-in-regular tournament of order n. Then $\gamma _{k}(T_{n})=2k$.

We now give a descriptive characterization of digraphs D satisfying $\gamma _{k}(D)=n-1$. We denote by $X_{k}$ the set of vertices of a digraph $D=(V,A)$, with in-degree at least k,  i.e.,

$$\begin{aligned} X_{k}=\left\{ x\in V:d_{D}^{-}\left( x\right) \ge k\right\} \text { and }Y_{k}=X_{k}-X_{k+1}=\left\{ x\in V:d_{D}^{-}\left( x\right) =k\right\} \text {.} \end{aligned}$$

Theorem 5

Let $D=(V,A)$ be a digraph of order n, and let k be a positive integer with $\Delta ^{-}\left( D\right) \ge k$. Then, $\gamma _{k}(D)=n-1$ if and only if $\left| X_{k+1}\right| \le 1$, $\left\langle X_{k}\right\rangle$ is a complete digraph, and if $X_{k+1}=\left\{ v\right\}$, then $v\Rightarrow Y_{k}$.

Proof

Necessity. If $\left| X_{k+1}\right| \ge 2$, then $X_{k+1}$ has two vertices say, x and y such that $V-\left\{ x,y\right\}$ is a k-dominating set of D, a contradiction.

Now, assume to the contrary that the underlying graph of $\left\langle X_{k}\right\rangle$ is not a complete digraph. This means that there exist two nonadjacent vertices in $X_{k}$, say x and y. It is clear that $V-\left\{ x,y\right\}$ is also a k-dominating set of D and we obtain a contradiction. Finally assume that $X_{k+1}=\left\{ v\right\}$ and there exists at least a vertex u in $Y_{k}$ such that $\left( v,u\right) \notin A$. Then $V-\left\{ u,v\right\}$ is a k-dominating set of D, again we obtain a contradiction.

Sufficiency. Suppose to the contrary that $\gamma _{k}(D)\ne n-1$. Let S be a $\gamma _{k}(D)$-set of D. Since $\Delta ^{-}\left( D\right) \ge k$, $\gamma _{k}(D)\le n-2$, which implies that $V-S$ has at least two vertices, say x and y. If x and y are in $Y_{k}$, then we obtain a contradiction with the fact that $\left\langle X_{k}\right\rangle$ is a complete digraph. Since $\left| X_{k+1}\right| \le 1$, we must have $x\in Y_{k}$ and $y\in X_{k+1}$ or $x\in X_{k+1}$ and $y\in Y_{k}$. So, without loss of generality, suppose that $X_{k+1}=\{y\}.$ Thus, $(y,x)\notin A$ which gives a contradiction with $y\Rightarrow Y_{k}$. $\square$

Corollary 2

Let D be a r-in-regular digraph of order $n\ge 2$ and k a positive integer with $r\ge k.$ Then, $\gamma _{k}(D)=n-1$ if and only if D is a k-in-regular complete digraph.

Proof

Let D be a r-in-regular digraph of order $n\ge 2$ and k a positive integer with $r\ge k.$ If $\gamma _{k}(D)=n-1$, then by Theorem 5, $r=k$ , otherwise, if $r\ge k+1$ then $Y_{k}=\emptyset$ and $V=X_{k+1}$. Thus, $n=\left| V\right| =\left| X_{k+1}\right| \le 1$, a contradiction with $n\ge 2$. So, D is a complete k-in-regular digraph. The converse is obvious, since we cannot have a k-dominating set S of a k-in-regular complete digraph with $\left| S\right| \le n-2$. $\square$

Corollary 3

Let D be an oriented graph of order n and k a positive integer with $\delta ^{-}\left( D\right) \ge k$. Then, $\gamma _{k}(D)=n-1$ if and only if D is k-in-regular tournament $T_{n}$ of order $n=2k+1$.

Proof

Let D be an oriented graph of order n and k a positive integer with $\delta ^{-}\left( D\right) \ge k\ge 1$. Then $V=X_{k}$, and by Theorem 5, D is a complete oriented digraph, which means that D is a tournament $T_{n}$. Suppose that D has a vertex v in $X_{k+1}$. Then $v\Rightarrow V-\left\{ v\right\}$, and so D has at least $\delta ^{-}\left( D\right)$ symmetrical arcs in D a contradiction. So, $X_{k+1}=\emptyset ,$ and thus $T_{n}$ is k-in-regular. By Observations 3, $n=2k+1$.

The converse is obvious. $\square$

In the next, we give an upper on $\gamma _{k}{\small (D)}$ for $\delta ^{-}\left( D\right) \ge k$, which generalizes the known upper bound $\gamma (D)\le \dfrac{2n}{3}$ given by Lee (1998), also we provide a descriptive characterization of digraphs attaining this bound. First, we recall an lower bound for the independence number due to Caro (1980) and Wei (1981), which is fundamental for our main result.

Theorem 6

(Wei 1981) If $G=(V,E)$ is a graph of order n, then

$$\begin{aligned} \alpha \left( G\right) \ge \sum \limits _{v\in V}\frac{1}{d_{G}\left( v\right) +1}\text {,} \end{aligned}$$

with equality if and only if every component of G is a complete graph.

Theorem 7

Let $D=\left( V,A\right)$ be a digraph of order n with $\delta ^{-}\left( D\right) \ge k$ and k a positive integer. Then,

$$\begin{aligned} \gamma _{k}{\small (D)\le }\frac{2k}{2k+1}n\text {,} \end{aligned}$$

with equality if and only if D is a disjoint union of copies of k-in-regular tournaments of order $2k+1$.

Proof

Let $D=\left( V,A\right)$ be a digraph of order n with $\delta ^{-}\left( D\right) \ge k$, where k is a positive integer. Let $H=\left( V,B\right)$ be a spanning digraph of D defined as follows: while there exists a vertex v in V of in-degree greater than k, we remove an arc incident to v. Finally, we obtain, $d^{-}\left( v\right) =k$ for every vertex $v\in V$ and so, H is k-in-regular. Now, let $G=\left( V,E\right)$ be the underlying graph of H. It follows from Theorem 6, that

$$\begin{aligned} \alpha \left( G\right) \ge \sum \limits _{v\in V}\frac{1}{d_{G}\left( v\right) +1}\ge \frac{n^{2}}{\sum \nolimits _{v\in V}(d_{G}\left( v\right) +1)}\text {.} \end{aligned}$$

(1)

Since $2\left| E\right| =\sum _{v\in V}d\left( v\right)$ and $\left| E\right| \le \left| B\right| =kn$,

$$\begin{aligned} \alpha \left( G\right) \ge \dfrac{n^{2}}{2\left| E\right| +n} \ge \dfrac{n^{2}}{2\left| B\right| +n}=\dfrac{n}{2k+1}\text {.} \end{aligned}$$

(2)

Let I be a $\alpha \left( H\right)$-set. Then every vertex in I has k-in-neighbors in $V-I$ and so, $V-I$ is a k-dominating set of H. Moreover, since $\alpha \left( G\right) =\alpha \left( H\right)$ and deleting an arc cannot decrease the k-domination number of D. The upper bound is then deduced by:

$$\begin{aligned} \gamma _{k}\left( D\right) \le \gamma _{k}(H)\le \left| V-I\right| =n-\alpha \left( G\right) \le \frac{2kn}{2k+1}\text {.} \end{aligned}$$

(3)

To prove equality, we begin with the sufficient condition. Let p be any positive integer and consider the digraph D consisting of the disjoint union of p copies of the k-in-regular tournaments of order $2k+1$. Then $n=\left( 2k+1\right) p$, and by Observation 4, we have $\gamma _{k}\left( D\right) =p\gamma _{k}(T_{2k+1})=2kp=\dfrac{2kn}{2k+1}$.

For the necessary condition, assume that $\gamma _{k}(D)=\dfrac{2kn}{2k+1}$. Then we have equality in (1)–(3). In particular,

$$\begin{aligned} \left| E\right| =\left| B\right| \text { and }\alpha \left( G\right) =\sum \limits _{v\in V}\frac{1}{d\left( v\right) +1}\text {.} \end{aligned}$$

(4)

The first equality in (4) implies that H is an oriented graph. By Theorem 6, the second equality implies that G has $\alpha \left( G\right) =\alpha$ components, each of which is a complete graph. Hence, H is a k-in-regular oriented graph, and every component of H, is a k-in-regular tournament $T_{r}^{j}$, for $j=1,\ldots ,\alpha$. By Observations 3 and 4 , we have $r=$$2k+1\ge 3$ and $\gamma _{k}(T_{2k+1}^{j})=2k$, for $j=1,\ldots ,\alpha$, respectively. Now to finish the proof of Theorem 7, we show that H is exactly D, i.e., $A=B$. To do this, assume to the contrary that D has at least an arc, say, $\left( y,x\right)$ which is not present in H, i.e., $\left( y,x\right) \in A$ but $\left( y,x\right) \notin B$, and without loss of generality assume that x is in $V\left( T_{2k+1}^{1}\right)$ and y my be in $V\left( T_{2k+1}^{1}\right)$ or not. Since $T_{2k+1}^{1}$ is a k-in-regular tournament of order at least three, x has at least an in-neighbor, say, $z\ne y$ in $V\left( T_{2k+1}^{1}\right) \$(note that in case $y\in V\left( T_{2k+1}^{1}\right)$, $\left( y,x\right)$ is a symmetrical arc of D). Thus, we can construct a k-dominating set of D by taking $V\left( T_{2k+1}^{1}\right) -\left\{ x,z\right\}$ and 2k vertices of each $T_{2k+1}^{j}$, for $j=2,\ldots ,\alpha$, among them y. Since $n=\left( 2k+1\right) \alpha$, we have, $\gamma _{k}\left( D\right) \le \left( 2k-1\right) +2k\left( \alpha -1\right) <\dfrac{2kn}{2k+1}$, a contradiction. Hence, D is a disjoint union of copies of k-in-regular tournaments of order $2k+1$. $\square$

Remark 1

For undirected graphs G of order n with $\delta \left( G\right) \ge k$ and k a positive integer, the bound, $\gamma _{k}\left( G\right) \le \dfrac{kn}{k+1}$ given by Cockayne et al. (1985), is true only if G is the underlying graph of a symmetrical digraph D. However, this inequality is not true for any digraph D with $\delta ^{-}\left( D\right) \ge k$. Consider the k-in-regular tournament $T_{n}$ of order $n=2k+1$. For this digraph, $\gamma _{k}\left( T_{n}\right) =2k=\dfrac{2kn}{2k+1}>\dfrac{kn}{k+1}$.

For the case $k=1$, we have the upper bound of Lee (1998). Note that the technique proof given in Theorem 7 is different from Lee’s technique proof.

Corollary 4

(Lee 1998) Let D be a digraph with order n and minimum in-degree $\delta ^{-}\left( D\right) \ge 1$. Then,

$$\begin{aligned} \gamma (D)\le \dfrac{2n}{3}\text {,} \end{aligned}$$

with equality if and only if D is a disjoint union of copies of $C_{3}$.