Abstract:

Let $G=(V, A)$ be a digraph with vertex set $V$ and arc set $A$. A set $D_{k}$ of vertices of $G$ is a $k$-tuple dominating set of $G$ if for every vertex $v\in V(G)\setminus D_{k}$, there exists $u_{i}\in D_{k}$ (possibly some vertex $u_{i}=v$) such that arcs $(u_{i},v)\in A(G)$ for $1\leq i\leq k$. The $k$-tuple domination number $\gamma_{\times k}(G)$ of $G$ is the cardinality of a minimum $k$-tuple dominating set of $G$. In this paper we present a new upper bound on the $k$-tuple domination number of generalized de Bruijn digraphs $G_B(n,d)$. Furthermore, the method of constructing a $k$-tuple dominating set of generalized de Bruijn digraph is given. %which improves the known upper bound in previous literature. For special generalized de Bruijn digraphs, we further improve the bounds on $k$-tuple domination number by directly constructing $k$-tuple dominating sets.

Key words: generalized de Bruijn digraphs, dominating set, k-tuple dominating set