Diameter-Preserving Spanning Trees in Sparse Weighted Graphs

We give a simple sufficient condition for a weighted graph to have a diameter-preserving spanning tree. More precisely, let G = (V, E, fE) be a connected edge weighted graph with fE being the edge weight function. Let fV be the vertex weight function of G induced by fE as follows: fV(v) = max{fE(e) : e is incident with v} for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${v \in V}$$\end{document} . We show that G contains a diameter-preserving spanning tree if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d(G)\ge \frac{2}{3} \sum_{v\in V} f_V(v)}$$\end{document} where d(G) is the diameter of G. The condition is sharp in the sense that for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon >0 }$$\end{document} , there exist weighted graphs G satisfying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d(G) > (\frac{2}{3}-\epsilon)\sum_{v\in V} f_V(v)}$$\end{document} and not containing a diameter-preserving spanning tree.