The k-tuple twin domination in de Bruijn and Kautz digraphs

A vertex it in a digraph G out-dominates itself and all vertices v such that (u, v) is an arc of G, similarly, u in-dominates both itself and all vertices w such that (w, u) is an arc of G. A set D of vertices of G is a twin dominating set of G if every vertex of G is out-dominated by a vertex of D and in-dominated by a vertex in D. In this paper, we introduce the k-tuple twin domination in directed graphs. A set D of vertices of G is a k-tuple twin dominating set if every vertex of G is out-dominated by at least k vertices in D and in-dominated by at least k vertices in D. We consider the problem of the k-tuple twin domination in de Bruijn and Kautz digraphs, and give construction methods for constructing minimum k-tuple twin dominating sets in these digraphs. (c) 2007 Elsevier B.V. All rights reserved.