Abstract:

Let G=(V, A) be a digraph with vertex set V and arc set A.  A set T of vertices of G is a twin dominating set of G if for every vertex v\in V(G)\setminus T, there exist u, w\in T (possibly u=w) such that arcs (u,v),(v,w)\in A(G). The twin domination number \gamma^{*}(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we present a new upper bound on the twin domination number of generalized de Bruijn digraphs G_B(n,d) and generalized Kautz digraphs G_K(n,d), which improves the known upper bound in previous literature. For special generalized de Bruijn and Kautz digraphs, we further improve the bounds on twin domination number by directly constructing their twin dominating sets.

Key words: generalized de Bruijn digraphs, generalized Kautz digraphs, dominating set, absorbant, twin dominating set