Premium
Minimum spanners of butterfly graphs
Author(s) -
Hwang ShienChing,
Chen GenHuey
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.5
Subject(s) - combinatorics , mathematics , metric dimension , chordal graph , indifference graph , bipartite graph , pathwidth , discrete mathematics , cograph , graph , 1 planar graph , line graph
Given a connected graph G , a spanning subgraph G′ of G is called a t ‐spanner 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 of edges among all t ‐spanners of G . 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 minimum t ‐spanners for the k ‐ary r ‐dimensional butterfly graphs for 2 ≤ t ≤ 6 and t = 8. © 2001 John Wiley & Sons, Inc.