On tree 3-spanners in directed path graphs
A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. While the complexity of the problem of recognizing whether a graph has a tree t-spanner is known for any fixed t 96 3, the case t = 3 is still open. H.-O. Le and V. B. Le (1999, Networks, 34(2), 81-87) have shown that every directed path graph admits a tree 3-spanner by proposing an algorithm to construct a tree 3-spanner of a given directed path graph. In this paper, we point out a flaw in their algorithm by producing a directed path graph for which their algorithm falls to produce a tree 3-spanner although the graph admits a tree 3-spanner. Furthermore, we show that directed path graphs need not admit tree 3-spanners in general. Next, we show that directed path graphs of diameter two always admit tree 2-spanners and hence tree 3-spanners. Finally, we show that a tree 2-spanner of a diameter two directed path graph can be constructed in linear time. (c) 2007 Wiley Periodicals, Inc.
directed path graphs spanning trees spanners tree spanners distance in graphs np-completeness