
doi: 10.1007/bf02570700
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\).
510.mathematics, Packing and covering in \(n\) dimensions (aspects of discrete geometry), Hadwiger number, minimum spanning tree, maximum vertex degree, Article, Trees
510.mathematics, Packing and covering in \(n\) dimensions (aspects of discrete geometry), Hadwiger number, minimum spanning tree, maximum vertex degree, Article, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 37 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
