Kautz网络中的路和宽距离

The Path and Wide-distance of Kautz Networks

用K(d,n)表示Kautz网络,该网络由于具有优良的拓扑性质而频频出现在文献中被广泛研究,本文针对该网络中的路和宽距离得到如下结论:设x和y是中两个不同的顶点,P是一条最短(x,y)-路。Q是一条最短(y,x)-路,那么(1)如果P和Q相交于不同于x和y的内部结点,那么|P|+|Q|>n;(2)P∪Q最多由3个圈的并组成;(3)如果有d(x,y)>=n-d+3,那么(d-1)-宽距离d_(d-1)(K(d,n):x,y)=n+1.作为结论(3)的一个应用,本文表明,如果d>=3和n<=d-2,那么独立数α_(l,d-1)(K(d,n))=α_(l,d)(K(d,n))=d^n+d^(n-1),其中l=1,2,…,n.

Let K（d, n） denote Kautz networks, which frequently appear in the literature because of its good teatures. This paper shows the following results. Let x and y be two distinct vertices of K（d, n）, P be a shortest （x, y）-path, Q be a shortest （y, x）-path, Then（1）｜P｜ ＋ ｜Q｜ 〉 n if P and Q intersect in a vertex other than x and y; （2） P ∪ Q consists of at most three cycles; （3） The wide-distance dd-1（K（d, n） ： x, y） = n ＋ 1 if d（x, y） 〉 n - d＋ 3. And using result （3）, we obtain the independence number αl,d-1（K（d, n）） = αl,d（K（d, n）） = d^n＋d^n-1for l =1, 2,.. , n if d≥ 3 and n ≤d-2.