×

A note on MAD spanning trees. (English) Zbl 0946.05025

A minimum average distance (MAD) spanning tree of a connected graph \(G\) has the minimum sum of the distances between all pairs of vertices. R. C. Entringer [J. Comb. Math. Comb. Comput. 24, 65-84 (1997; Zbl 0880.05029)] raised the following questions. (1) Does every \(G\) have a MAD spanning tree that is also distance preserving from some vertex? (2) If \(G\) has a MAD spanning tree that is distance preserving, is it distance preserving from a median vertex? In this paper both questions are settled in the negative.

MSC:

05C05 Trees
05C12 Distance in graphs

Citations:

Zbl 0880.05029