On the k-tuple domination of generalized de Brujin and Kautz digraphs

A vertex u in a digraph G = (VA) is said to dominate itself and vertices v such that (u, v) is an element of A. For a positive integer k, a k-tuple dominating set of G is a subset D of vertices such that every vertex in G is dominated by at least k vertices in D. The k-tuple domination number of G is the minimum cardinality of a k-tuple dominating set of G. This paper deals with the k-tuple domination problem on generalized de Bruijn and Kautz digraphs. We establish bounds on the k-tuple domination number for the generalized de Bruijn and Kautz digraphs and we obtain some conditions for the k-tuple domination number attaining the bounds. (C) 2010 Elsevier Inc. All rights reserved.