A spanning tree of a graph is distance #kappa#-approximating whenever the distance of every two vertices in the graph or in the tree differs by at most #kappa#. Variants or modifications of a simple approach yield distance #kappa#-approximating spanning trees for block graphs, intervalgraphs, distance-hereditary graphs, and cocomparability graphs, with #kappa#=1,2,2,4. On the other hand, there are chordal graphs without distance #kappa#-approximating spanning tree for arbitrary large #kappa#.
展开▼
