Spanners in graphs of bounded degree

Given a graph G = ( V, E ), a subgraph S = ( V, E s ) is a t ‐spanner of G if for every edge xy ϵ E the distance between x and y in S is at most t . Spanners have applications in communication networks, distributed systems, parallel computation, and many other areas. This paper is concerned with the complexity of finding a minimum size t ‐spanner in a graph with bounded degree. A linear time algorithm is presented for finding a minimum‐size 2‐spanner in any graph whose maximum degree is at most four. The algorithm is based on a graph theoretical result concerning edge partition of a graph into a “triangle‐free component” and “triangular‐components.” On the other hand, it is shown that to determine whether a graph with maximum degree at most nine contains a t ‐spanner with at most K edges ( K is given) is NP‐complete for any fixed t ⩾ 2. © 1994 by John Wiley & Sons, Inc.