A note on lower bounds for the total domination number of 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. 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⁺₁ + d⁺₂ + · · · + d⁺_k ) ≥ |V (D)|}, where d⁺₁ , d⁺₂ , . . . , 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.