Bounds on the domination number of a digraph

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of D, denoted by $$\gamma (D)$$ γ ( D ) , is the minimum cardinality of a dominating set of D. The Slater number $$s\ell (D)$$ s ℓ ( D ) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing out-degree sequence of D is at least as large as the order of D. For any digraph D of order n with maximum out-degree $$\Delta ^+$$ Δ + , it is known that $$\gamma (D)\ge \lceil n/(\Delta ^++1)\rceil $$ γ ( D ) ≥ ⌈ n / ( Δ + + 1 ) ⌉ . We show that $$\gamma (D)\ge s\ell (D)\ge \lceil n/(\Delta ^++1)\rceil $$ γ ( D ) ≥ s ℓ ( D ) ≥ ⌈ n / ( Δ + + 1 ) ⌉ and the difference between $$s\ell (D)$$ s ℓ ( D ) and $$\lceil n/(\Delta ^++1)\rceil $$ ⌈ n / ( Δ + + 1 ) ⌉ can be arbitrarily large. In particular, for an oriented tree T of order n with $$n_0$$ n 0 vertices of out-degree 0, we show that $$(n-n_0+1)/2\le s\ell (T)\le \gamma (T)\le 2s\ell (T)-1$$ ( n - n 0 + 1 ) / 2 ≤ s ℓ ( T ) ≤ γ ( T ) ≤ 2 s ℓ ( T ) - 1 and moreover, each value between the lower bound $$s\ell (T)$$ s ℓ ( T ) and the upper bound $$2s\ell (T)-1$$ 2 s ℓ ( T ) - 1 is attainable by $$\gamma (T)$$ γ ( T ) for some oriented trees. Further, we characterize the oriented trees T for which $$s\ell (T)=(n-n_0+1)/2$$ s ℓ ( T ) = ( n - n 0 + 1 ) / 2 hold and show that the difference between $$s\ell (T)$$ s ℓ ( T ) and $$(n-n_0+1)/2$$ ( n - n 0 + 1 ) / 2 can be arbitrarily large. Some other elementary properties involving the Slater number are also presented.