Graphs that admit a unique tree t-spanner
by
Ioannis Papoutsakis
University of Toronto

A tree t-spanner of a graph G is a spanning tree of G, in which the distance between every pair of vertices is at most t times their distance in G. The tree t-spanner problem is to determine if a given graph admits a tree t-spanner. This problem is tractable when t <= 2, while it is NP-complete when t >= 4. First, for each t, we provide a characterization of graphs that admit a tree t-spanner in terms of decomposition. Second, we apply this characterization to provide nontrivial (note that a tree admits a unique tree t-spanner for every t) examples of graphs that admit a unique tree t-spanner.

Date received: April 19, 2001