Minimum spanners of butterfly graphs
Shien‐Ching Hwang, Gen-Huey Chen · Networks · 2001
Abstract Given a connected graphG, a spanning subgraphG′ofGis called at‐spanner if every pair of two adjacent vertices inGhas a distance of at mosttinG′. At‐spanner of a graphGis minimum if it contains minimum number of edges among allt‐spanners ofG. Finding minimum spanners for general graphs is rather difficult. Most of previous results were obtained for some particular graphs, for example, butterfly graphs, cube‐connected cycles, de Bruijn graphs, Kautz graphs, complete bipartite graphs, and permutation graphs. The butterfly graphs were originally introduced as the underlying graphs of FFT networks which can perform the fast Fourier transform (FFT) very efficiently. In this paper, we successfully construct most of the minimumt‐spanners for thek‐aryr‐dimensional butterfly graphs for 2 ≤t≤ 6 andt= 8. © 2001 John Wiley & Sons, Inc.