广义de Bruijn和Kautz有向图的距离控制数(英文)  

Distance Domination Numbers of Generalized de Bruijn and Kautz Digraphs

作　　者：田方[1] 徐俊明[2] 

机构地区：[1]上海财经大学应用数学系,上海200433 [2]中国科学技术大学数学系,合肥230026

出　　处：《运筹学学报》2006年第1期88-94,共7页Operations Research Transactions

基　　金：The work was supported partially by NNSF of China (No.10271114).

摘　　要：对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .The distance l-domination number rl（G） of a strongly connected digraph G is the minimum number r for which there is a set D 包含 V（G） with cardinality r such that any vertex v 不属于 D can be reached within distance l from some vertex in D. In this paper, we establish a lower bound and an upper bound for rl of a generalized de Bruijn digraph and a generalized Kautz digraph, and also give a sufficient condition for these digraphs whose r2 are equal to the lower bounds. As a consequence, for the de Bruijn digraph B（d, k）, we determine that r2（B（d, k）） = [d^k/（d^2＋d＋1）] . At the end of this paper, we conjecture r2（K（d,k））=[（d^k＋d^k-1）/（d^2＋d＋1）]

关 键 词：运筹学 距离控制数 控制数 广义de BRUIJN有向图 广义Kautz有向图 

分 类 号：O157.5[理学—数学] TS952.834[理学—基础数学]