On tree 3‐spanners in directed path graphs
Bhawani Sankar Panda, Anita Das · Networks · 2007
Abstract 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≠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 fails 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. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 203–210 2007