Total domination in 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. A dominating set S of D is called a total dominating set of D if the subdigraph of D 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 if D is a rooted tree, a connected contrafunctional digraph or a strongly connected digraph of order n ≥ 2, then γt(D) ≤ 2(n + 1)/3 and if D is a digraph of order n with minimum in-degree at least one whose connected components are isomorphic to neither c̅₂ nor c̅₅, then γt(D) ≤ 3n/4, where c̅₂ and c̅₅ denote the directed cycles of order 2 and 5 respectively. Moreover, we characterize the corresponding digraphs achieving these upper bounds. 

Keywords: Total domination, rooted tree, contrafunctional digraph, directed graph