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 , where 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 n₀ vertices of out-degree 0, we show that γ_t(T ) ≥ sℓ⁺ (T ) ≥ 2(n − n₀ + 1)/3 and the difference between sℓ⁺(T ) and 2(n − n₀ + 1)/3 is also arbitrarily large.