SPANNERS OF HYPERCUBE-DERIVED NETWORKS

A spanning subgraph G' of a simple undirected graph G is a t-spanner o f G if every pair of vertices that are adjacent in G are at distance a t most t in G'. The parameter t is called the dilation of the spanner. Spanners with small dilations have many applications, such as their u se as low-cost approximations of communication networks with only smal l degradations in performance. In this paper, we derive spanners with small dilations for four closely related bounded-degree approximations of hypercubes: butterflies, cube-connected cycles, binary de Bruijn g raphs, and shuffle-exchange graphs. We give both direct constructions and methods for deriving spanners for one class of graphs from spanner s for another class. We prove that most of our spanners are minimum in the sense that spanners with fewer edges have larger dilations.