Diameter-Preserving Spanning Trees in Sparse Weighted Graphs

作者：Liu, Yue^*; Huang, Jing

来源：Graphs and Combinatorics, 2009, 25(5): 753-758.

DOI：10.1007/s00373-010-0887-z

• Diameter-preserving spanning tree
• Weighted graph
• Shortest-paths tree
• Minimum diameter spanning tree

We give a simple sufficient condition for a weighted graph to have a diameter-preserving spanning tree. More precisely, let G = (V, E, f(E)) be a connected edge weighted graph with f(E) being the edge weight function. Let f(V) be the vertex weight function of G induced by f(E) as follows: f(V)(v) = max{f(E)(e) : e is incident with v} for all v is an element of V. We show that G contains a diameter-preserving spanning tree if d(G) >= 2/3 Sigma(v is an element of V) f(V)(v) where d(G) is the diameter of G. The condition is sharp in the sense that for any is an element of > 0, there exist weighted graphs G satisfying d(G) > (2/3-is an element of) Sigma(v is an element of V) f(V)(v) and not containing a diameter-preserving spanning tree.

• 出版日期2009-11
• 单位同济大学