Bounds on the Domination Number of a Digraph and its Reverse

Michitaka Furuya


Let $D$ be a digraph.
A dominating set of $D$ is the subset $S$ of $V(D)$ such that each vertex in $V(D)-S$ is an out-neighbor of a vertex in $S$.
The minimum cardinality of a dominating set of $G$ is denoted by $\gamma (D)$.
We let $D^{-}$ denote the reverse of $D$.

In [Discrete Math. {\bf 197/198} (1999) 179--183], Chartrand, Harary and Yue proved that every connected digraph $D$ of order $n\geq 2$ satisfies $\gamma (D)+\gamma (D^{-})\leq \frac{4n}{3}$ and characterized the digraphs $D$ attaining the equality.
In this paper, we pose a reduction of the determining problem for $\gamma (D)+\gamma (D^{-})$ using the total domination concept.
As a corollary of such a reduction and known results, we give new bounds for $\gamma (D)+\gamma (D^{-})$ and an alternative proof of Chartrand-Harary-Yue theorem.

Full Text:



  • There are currently no refbacks.