2017/12/10 by Lan Lin, Lin, Lan, Yixun Lin +1
Computer Science · Mathematics · #05C35 #90C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems #math.CO #msc:05C35 #msc:90C35
paper · pdf · doi:10.48550/arxiv.1712.03497
16 pages, 7 figures
arxiv created 2017/12/10 · openalex publication_date 2017/12/10 · arxiv updated 2017/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With applications in distribution systems and communication networks, the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized. The problem has been proved to be NP-hard and fixed-parameter polynomial algorithms have been obtained for some special classes of graphs. In this paper, we concentrate on the optimality characterizations for typical classes of graphs. We determine the exact optimality representations for Petersen graph, the complete k-partite graphs, split graphs, generalized convex graphs, and several planar grids, including rectangular grids, triangular grids, and triangular-rectangular grids.