The k-tuple twin domination in generalized de Bruijn and Kautz networks

Given a digraph (network) G = (V A), a vertex u in G is said to out-dominate itself and all vertices v such that the arc (u. v) E A; similarly, u in-dominates both itself and all vertices in such that the arc (w, u) is an element of A. A set D of vertices of G is a k-tuple twin dominating set if every vertex of G is out-dominated and in-dominated by at least k vertices in D, respectively. The k-tuple twin domination problem is to determine a minimum k-tuple twin dominating set for a digraph. In this paper we investigate the k-tuple twin domination problem in generalized de Bruijn networks G(B)(n, d) and generalized Kautz G(K) (n, d) networks when d divides n. We provide construction methods for constructing minimum k-tuple twin dominating sets in these networks. These results generalize previous results given by Araki [T. Araki, The k-tuple twin domination in de Bruijn and Kautz digraphs, Discrete Mathematics 308 (2008) 6406-6413] for de Bruijn and Kautz networks. (C) 2011 Elsevier Ltd. All rights reserved.