Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction Original Research Article

A spanning tree image of a graph image is called a treeimage-spanner, if the distance between any two vertices in image is at most image-times their distance in image. A graph that has a tree image-spanner is called a treeimage-spanner admissible graph. The problem of deciding whether a graph is tree image-spanner admissible is NP-complete for any fixed image, and is linearly solvable for image and image. The case image still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal image vertex separator for every pair of non-adjacent vertices image and image are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81–87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203–210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.