The authors revive an older topic and consider a problem of practical significance. The older topic refers to spanning tree–related problems. The problem of practical significance relates to communication networks. Given a graph G, a spanning tree of G is a connected graph without cycles. The diameter of a weighted graph G is the longest among the shortest paths of all pairs of vertices in the graph G. Let G be a graph and W ( e ) be the weight of each edge e in G. The minimum diameter spanning tree (MDST) problem requires finding a spanning tree T for G such that where p is the simple path, is minimized.

The authors give a characterization for a Euclidean graph G that solves the MDST problem for these special graphs. In this case, the MDST problem for these special graphs is called a geometric MDST problem.

Further, the authors prove that given an upper bound C for the total weight and an upper bound D for the diameter, the problem of determining if a spanning tree exists for an undirected graph is NP-complete.

The authors conclude the paper with two open problems. The proofs are short but involved. An unusually large number of acronyms are used in this paper, which is unavoidable. Keeping track of the meanings of all these acronyms makes the paper tough to read. This paper will be of interest primarily to researchers in the area of spanning trees. In spite of the applied nature of the result, the paper is too mathematical for many to follow. The references are adequate.