On the Sum of Out-Domination Number and In-Domination Number of Digraphs

Abstract

A vertex subset $S$ of a digraph $D=(V,A)$ is called an out-dominating (resp.,in-dominating) set of $D$ if every vertex in $V–S$ is adjacent from (resp., to) some vertex in $S$. The out-domination (resp., in-domination) number of $D$, denoted by ${\gamma }^{+}(D)$ (resp.,${\gamma }^{-}(D)$), is the minimum cardinality of an out-dominating (resp., in-dominating) set of $D$. In 1999, Chartrand et al. proved that ${\gamma }^{+}(D)+{\gamma }^{-}(D)\le \frac{4n}{3}$ for every digraph $D$ of order $n$ with no isolated vertices. In this paper, we determine the values of ${\gamma }^{+}(D)+{\gamma }^{-}(D)$ for rooted trees and connected contrafunctional digraphs $D$, based on which we show that ${\gamma }^{+}(D)+{\gamma }^{-}(D)\le \frac{(2k+2)n}{2k+1}$ for every digraph $D$ of order $n$ with minimum out-degree or in-degree no less than $1$, where $2k+1$ is the length of a shortest odd directed cycle in $D$. Our result partially improves the result of Chartrand et al. In particular, if $D$ contains no odd directed cycles, then ${\gamma }^{+}(D)+{\gamma }^{-}(D)\le n$.