广义de Bruijn有向图的k-元控制集

$G=(V, A)$ 表示一个有向图, 其中 $V$ 和 $A$ 分别表示有向图 $G$ 的点集和弧集。 对集合 $D_{k}\subseteq V(G)$, 如果对于任意点 $v\in V(G)$, 都存在 $k$ 个点 $u_{i}$, $1\leq i\leq k$ (可能存在某个 $u_{i}$ 和 $v$ 是同一点) 使得 $(u_{i},v)\in A(G)$, 则称 $D_{k}$ 是 $G$ 的一个 $k$-元控制集。 有向图 $G$ 的 $k$-元控制数 $\gamma_{\times k}(G)$ 是 $G$ 的最小 $k$-元控制集所含点的数目。 给出了广义 de Bruijn 有向图的 $k$-元控制数的新上界, 并且具体给出了构造广义 de Bruijn 有向图的 $k$-元控制集的方法。 此外, 对某些特殊的广义 de Bruijn 有向图, 通过构造其 $k$-元控制集, 进一步改进了它们 $k$-元控制数的上界。

k-tuple domination in generalized de Bruijn digraphs

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.