On the bounded domination number of tournaments

Abstract

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γk(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γk(T) = [n/(k + 1)] when T is a tournament with n ≥ 14k 1gk vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most 1gn-1g1gn + 2 vertices. © 2000 Elsevier Science B.V. All rights reserved.