Low-degree minimum spanning trees (Q1895968): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:08, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Low-degree minimum spanning trees |
scientific article |
Statements
Low-degree minimum spanning trees (English)
0 references
27 November 1995
0 references
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\).
0 references
maximum vertex degree
0 references
minimum spanning tree
0 references
Hadwiger number
0 references