Shortest paths of butterfly graphs

摘要

An r-dimensional k-ray butterfly graph contains r levels, numbered 0,1,..., r-1, each of k~r vertices. Each vertex is uniquely represented by a pair <1, #beta#_0#beta#_1...#beta#_r-1>, where l implied by {0,1,...,r-1} is the level of the vertex and #beta#_0#beta#_1...#beta#_r-1 is a k-ary sequence of r symbols. Two vertices and are adjacent if and only if l'ident to l+1 (mod r) and #beta#_i=#beta#'_i for all 0<=i<=r-1 and i not =l. In this paper, a shortest path between arbitrary two vertices of an r-dimensional k-ary butterfly graph is determined.