Kautz网络中的路和宽距离

用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.