Premium
On tree 3‐spanners in directed path graphs
Author(s) -
Panda B.S.,
Das Anita
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20198
Subject(s) - spanner , combinatorics , gomory–hu tree , k ary tree , tree (set theory) , mathematics , spanning tree , path (computing) , shortest path tree , graph , directed graph , computer science , discrete mathematics , tree structure , binary tree , computer network , distributed computing
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