Minimum spanners of butterfly graphs

Given a connected graph G, a spanning subgraph G ' of G is called a t-spann er if every pair of two adjacent vertices in G has a distance of at most t in G '. A t-spanner of a graph G is minimum if it contains minimum number o f edges among all t-spanners of G. Finding minimum spanners for general gra phs is rather difficult. Most of previous results were obtained for some pa rticular graphs, for example, butterfly graphs, cube-connected cycles, de B ruijn graphs, Kautz graphs, complete bipartite graphs, and permutation grap hs. The butterfly graphs were originally introduced as the underlying graph s of FFT networks which can perform the fast Fourier transform (FFT) very e fficiently. In this paper, we successfully construct most of the minimum t- spanners for the k-ary r-dimensional butterfly graphs for 2 less than or eq ual to t less than or equal to 6 and t = 8. (C) 2001 John Wiley & Sons, Inc .