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 γ(D). We let D − denote the reverse of D. In [Discrete Math. 197/198 (1999) 179–183], Chartrand, Harary and Yue proved that every connected digraph D of order n ≥ 2 satisfies γ(D) + γ(D −) ≤ 4n 3 and characterized the digraphs D attaining the equality. In this paper, we pose a reduction of the determining problem for γ(D) + γ(D −) using the total domination concept. As a corollary of such a reduction and known results, we give new bounds for γ(D) + γ(D −) and an alternative proof of Chartrand-Harary-Yue theorem.