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)=\lceil \frac{n}{2}\rceil$. Moreover, we show that for every digraph $D$ of order $n$ with minimum in-degree at least one, $\gamma (D)\le \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)\le \frac{n}{2}$.