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 is-an-element-of E the distance between x and y in S is at most t. Spanners have applications in communication network s, distributed systems, parallel computation, and many other areas. Th is paper is concerned with the complexity of finding a minimum size t- spanner in a graph with bounded degree. A linear time algorithm is pre sented 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 co mponent'' and ''triangular-components.'' On the other hand, it is show n that to determine whether a graph with maximum degree at most nine c ontains a t-spanner with at most K edges (K is given) is NP-complete f or any fixed t greater-than-or-equal-to 2. (C) 1994 John Wiley & Sons, Inc.