English

运筹学学报 ›› 2021, Vol. 25 ›› Issue (2): 127-134.doi: 10.15960/j.cnki.issn.1007-6093.2021.02.010

•   • 上一篇    下一篇

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

董艳侠1, 薛涛1, 张广2,()   

  1. 1. 上海对外经贸大学统计与信息学院, 上海 201620
    2. 上海理工大学管理学院, 上海 200093
  • 收稿日期:2020-11-13 出版日期:2021-06-15 发布日期:2021-05-06
  • 通讯作者: 张广 E-mail:g.zhang@usst.edu.cn
  • 作者简介:张广 E-mail: g.zhang@usst.edu.cn
  • 基金资助:
    国家自然科学基金(11801361);上海市自然科学基金(18ZR1416300)

k-tuple domination in generalized de Bruijn digraphs

Yanxia DONG1, Tao XUE1, Guang ZHANG2,()   

  1. 1. School of Statistics and Information, Shanghai University of International Business and Economics, Shanghai 201620, China
    2. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Received:2020-11-13 Online:2021-06-15 Published:2021-05-06
  • Contact: Guang ZHANG E-mail:g.zhang@usst.edu.cn

RichHTML

7

PDF

131

摘要：

$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$-元控制数的上界。

关键词: 广义de Bruijn有向图, 控制集, k-元控制集

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

中图分类号: