Minimum tree-stretch of Hamming graphs and higher-dimensional grids

2018/07/22 by Lan Lin, Lin, Lan, Yixun Lin +1
Mathematics · #05C78 #68M10 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C78 #msc:68M10 #msc:68R10

paper · pdf · doi:10.48550/arxiv.1807.08252

14 pages, 4 figures

arxiv created 2018/07/22 · arxiv updated 2018/07/24

Abstract

The minimum stretch spaning tree problem for a grah G is to find a spaning tree T of G such as that the maximum distance in T between two adjacent vertices is minimized. The minimum value of this optimization problem gives rise to a grpah invariant σ T(G) called the tree stretch of G. The problem has been studied in the algorithmic aspects, such as NP-hardness and fixed-parameter solvability. This paper presents the exact values σ T(G) of hamming graphs Kn1 * Kn2 * ... * Knd and the higer-dimensional grids Pn1 * Pn2 * ... * Pnd.

Related

• The minimum stretch spanning tree problem for typical graphs
• On Minimum Average Stretch Spanning Trees in Polygonal 2-trees
• Stretching Stretch
• Optimal Euclidean Tree Covers
• Low-stretch spanning trees of graphs with bounded width