广义de Bruijn和Kautz有向图的距离控制数

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

Distance Domination Numbers of Generalized de Bruijn and Kautz Digraphs

The distance e-domination number γe(G) of a strongly connected digraph G is theminimum number γfor which there is a set D ∈V(G) with cardinality γ such that any vertex v ∈D can be reached within distance e from some vertex in D. In this paper, we establish a lower bound and an upper bound for γe of a generalized de Bruijn digraph and a generalized Kautz digraph, and also give a sufficient condition for these digraphs whose γ2 are equal to the lower bounds. As a consequence, for the de Bruijn digraph B(d,k),we determine that γ2(K(d,k)) = dk＋dk-1/d2＋d＋1].At the end of this paper,we conjecture γ2(K(d,k)) = dk＋dk-1/d2＋d＋1].