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

k-tuple domination in generalized de Bruijn digraphs

作　　者：董艳侠 薛涛 张广 DONG Yanxia;XUE Tao;ZHANG Guang(School of Statistics and Information,Shanghai University of International Business and Economics,Shanghai 201620,China;School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海对外经贸大学统计与信息学院,上海201620 [2]上海理工大学管理学院,上海200093

出　　处：《运筹学学报》2021年第2期127-134,共8页Operations Research Transactions

基　　金：国家自然科学基金(No.11801361);上海市自然科学基金(No.18ZR1416300)。

摘　　要：G=(V,A)表示一个有向图,其中V和A分别表示有向图G的点集和弧集。对集合Dk■V(G),如果对于任意点v∈V(G),都存在k个点ui,1≤i≤k(可能存在某个ui和v是同一点)使得(ui,v)∈A(G),则称Dk是G的一个k-元控制集。有向图G的k-元控制数γ×k(G)是G的最小k-元控制集所含点的数目。给出了广义de Bruijn有向图的k-元控制数的新上界,并且具体给出了构造广义de Bruijn有向图的k-元控制集的方法。此外,对某些特殊的广义de Bruijn有向图,通过构造其k-元控制集,进一步改进了它们k-元控制数的上界。Let G=(V,A)be a digraph with vertex set V and arc set A.A set Dk of vertices of G is a k-tuple dominating set of G if for every vertex v∈V(G)\Dk,there exists ui∈Dk(possibly some vertex ui=v)such that arcs(vi,v)∈A(G)for 1≤i≤k.The k-tuple domination numberγ×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 ktuple domination number of generalized de Bruijn digraphs GB(n,d).Furthermore,the method of constructing a k-tuple dominating set of generalized de Bruijn digraph is given.For special generalized de Bruijn digraphs,we further improve the bounds on k-tuple domination number by directly constructing k-tuple dominating sets.

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

分 类 号：O157.5[理学—数学]