On the Domination Number of Digraphs

Abstract

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)\), is the minimum cardinality of a dominating set of \(D\). We characterize the rooted trees and connected contrafunctional digraphs \(D\) of order \(n\) satisfying \(\gamma(D) = \left\lceil \frac{n}{2}\right\rceil\). Moreover, we show that for every digraph \(D\) of order \(n\) with minimum in-degree at least one, \(\gamma(D) \leq \frac{(k+1)n}{2k+1}\), where \(2k+1\) is the length of a shortest odd directed cycle in \(D\), and we characterize the corresponding digraphs achieving this upper bound. In particular, if \(D\) contains no odd directed cycles, then \(\gamma(D) \leq \frac{n}{2}\).