The Path and Wide-distance of Kautz Networks
Liu Er-gen · Advances in Mathematics · 2008
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 d_(d-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-1) for l=1,2,...,n if d=3 and n=d-2.