Low-degree minimum spanning trees (Q1895968)

The paper studies the maximum vertex degree of a minimum spanning tree (MST) in the spaces with \(L_p\) norm. It is proved that the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball, whereby the Hadwiger number \(H(B)\) of an open convex set \(B\) is the maximum number of neighbors of \(B\) considered over all packings of translates of \(B\). This result is not new; see the reviewer [Rostocker Math. Kolloq. 39, 89-93 (1990; Zbl 0737.05042)] and [Optimization 22, No. 2, 291-296 (1991; Zbl 0739.05029)]. Moreover, the paper studies the maximum vertex degree of MSTs in the space with rectilinear norm and proves that this number is equal to 8 in the plane, to 18 in the three-dimensional space, and grows exponentially in the dimension of the space. Also it is shown that for each dimension \(d\) there is a number \(p\) such that the maximum degree of a minimum degree MST over any finite set of points in the \(d\)-dimensional space with \(L_p\) norm exceeds \(2^d\).