On the sum of the total domination numbers of a diagraph and its converse

Abstract

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S has an in-neighbor in S. A dominating set S of D is called a total dominating set of D if the subdigraph induced by S has no isolated vertices. The total domination number of D, denoted by γt(D), is the minimum cardinality of a total dominating set of D. We show that for any connected digraph D of order n ≥ 3,γt(D) + γt(D−) ≤ 5n/3, where D− is the converse of D. Furthermore, we characterize the oriented trees for which the equality holds.

Mathematics Subject Classification (2010): 05C69, 05C20.

Key words: Total domination number, oriented tree, digraph, converse.