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

Distance Domination Numbers of Generalized de Bruijn and Kautz Digraphs

对于任意的正整数(?),强连通图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）]