  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.
