Tree 3-spanners of diameter at most 5

Original · EN

Tree spanners approximate distances within graphs; a subtree of a graph is a tree t-spanner of the graph if and only if for every pair of vertices their distance in the subtree is at most t times their distance in the graph. When a graph contains a subtree of diameter at most t, then trivially admits a tree t-spanner. Now, determining whether a graph admits a tree t-spanner of diameter at most t+1 is an NP complete problem, when t≥ 4, and it is tractable, when t≤ 3. Although it is not known whether it is tractable to decide graphs that admit a tree 3-spanner of any diameter, an efficient algorithm to determine graphs that admit a tree 3-spanner of diameter at most 5 is presented. Moreover, it is proved that if a graph of diameter at most 3 admits a tee 3-spanner, then it admits a tree 3-spanner of diameter at most 5. Hence, this algorithm decides tree 3-spanner admissibility of diameter at most 3 graphs.