English

运筹学学报

• 运筹学 • 上一篇    下一篇

广义de Bruijn和Kautz有向图的双向控制集

董艳侠1,2  张广3  单而芳3,*   

  1. 1. 上海对外经贸大学统计与信息学院, 上海 201620; 2. 上海大学数学系, 上海 200444; 3. 上海大学管理学院, 上海 200444,
  • 收稿日期:2015-11-13 出版日期:2016-09-15 发布日期:2016-09-15
  • 通讯作者: 单而芳 efshan@shu.edu.cn
  • 基金资助:

    国家自然科学基金 (Nos. 11571222, 11471210)

Twin domination in generalized de Bruijn and Kautz digraphs

DONG Yanxia1,2  ZHANG Guang3 SHAN Erfang3,*   

  1. 1. School of Statistics and Information, Shanghai University of International Business and Economics, Shanghai 201620, China; 2. Department of Mathematics, Shanghai University, Shanghai 200444, China; 3. School of Management, Shanghai University, Shanghai 200444, China
  • Received:2015-11-13 Online:2016-09-15 Published:2016-09-15

PDF

374

摘要：

设G=(V, A)是一个有向图, 其中V和A分别表示有向图G的点集和弧集. 对集合T\subseteq V(G), 如果对于任意点v\in V(G)\setminus T, 都存在点u, w\in T (u,w可能是同一点) 使得(u,v),(v,w)\in A(G), 则称T是G的一个双向控制集. 有向图G的双向控制数\gamma^{*}(G) 是G 的最小双向控制集所含点的数目. 提出了广义de Bruijn和Kautz有向图的双向控制数的新上界, 改进了以前文献中提出的相关结论. 此外, 对某些特殊的广义de Bruijn和Kautz有向图, 通过构造其双向控制集, 进一步改进了它们双向控制数的上、下界.

关键词: 广义de Bruijn有向图, 广义Kautz有向图, 控制集, 吸收集, 双向控制集

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