Main Article Content

A note on lower bounds for the total domination number of digraphs


Guoliang Hao
Xiaodan Chen

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. In this note, we introduce a new parameter, called the out-Slater number of a digraph D, which is defined by sℓ+(D) = min{k : ⌊k/2⌋ + (d+1 + d+2 + · · · + d+k ) ≥ |V (D)|}, where d+1 , d+2 , . . . , d+k are the first k largest out-degrees of D. Then we prove that if D is a digraph of order n with maximum out-degree Δ+ and with no isolated vertices, then γt(D) ≥ sℓ+(D) ≥ ⌈2n/(2Δ+ + 1)⌉ and the difference between sℓ+(D) and ⌈2n/(2Δ+ + 1)⌉ can be arbitrarily large, which improves a known lower bound by Arumugam et al. In particular, for an oriented tree T of order n ≥ 2 with n0 vertices of out-degree 0, we show that γt(T ) ≥ sℓ+(T ) ≥ 2(n − n0 + 1)/3 and the difference between sℓ+(T ) and 2(n − n0 + 1)/3 is also arbitrarily large.

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

Key words: Total domination number, directed graph, oriented tree, out-degree, out-
Slater number.


Journal Identifiers


eISSN: 1727-933X
print ISSN: 1607-3606