2015/03/20 by Ioannis Papoutsakis, Papoutsakis, Ioannis
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Topological and Geometric Data Analysis #cs.DM
paper · pdf · doi:10.48550/arxiv.1503.06063
arxiv created 2015/03/20 · openalex publication_date 2015/03/20 · arxiv updated 2015/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph that contains a spanning tree of diameter at most t clearly admits a tree t-spanner, since a tree t-spanner of a graph G is a sub tree of G such that the distance between pairs of vertices in the tree is at most t times their distance in G. In this paper, graphs that admit a tree t-spanner of diameter at most t+1 are studied. For t equal to 1 or 2 the problem has been solved. For t=3 we present an algorithm that determines if a graph admits a tree 3-spanner of diameter at most 4. For t≥4 it is proved that it is an NP-complete problem to decide whether a graph admits a tree t-spanner of diameter at most t+1.