The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach. (English) Zbl 0755.60011

Given \(n\) uniformly and independently distributed points in the \(d\)- dimensional cube of unit volume, it is well established that the length of the minimum spanning tree (MST) on these \(n\) points is asymptotic to \(\beta_{\text{MST}}(d)\cdot n^{(d-1)/d}\), where the constant \(\beta_{\text{MST}}(d)\) depends only on the dimension \(d\). One of the important open problems in this area is the exact determination of \(\beta_{\text{MST}}\). The paper is structured as follows. In Section 2 the authors introduce conditions under which the MST constant is characterized as a series expansion. In Section 3 the authors obtain an exact expression for \(\beta_{\text{MST}}(d)\) on a torus. In Sections 4, 5 an expansion for \(\beta_{\text{MST}}(d)\) in the independent model and better bounds for the MST in the plane are found. The last section includes some concluding remarks.
Reviewer: V.Oganyan (Erevan)


60D05 Geometric probability and stochastic geometry
90C27 Combinatorial optimization
Full Text: DOI