Quaestiones Mathematicae

Log in or Register to get access to full text downloads.

Remember me or Register

DOWNLOAD FULL TEXT Open Access  DOWNLOAD FULL TEXT Subscription or Fee Access

Total domination in digraphs

Guoliang Hao


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 neither2 nor5, then γt(D) ≤ 3n/4, where2 and5denote 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
AJOL African Journals Online