2
$\begingroup$

Are there any Euclidean spaces, in which the maximal vertex degree of MSTs (Minimum Spanning Trees) of a finite set of points and edge weights equal to Euclidean distance, isn't equal to the kissing number?

Remark:
The fact, that the kissing number is an upper bound on the vertex degree of MSTs of Euclidean spaces can be exploited for reducing the memory footprint for calculating those MSTs; instead of feeding $\frac{n(n-1)}{2}$ distances into the MST algorithm, it suffices to provide only the $k$ smallest distances for each vertex, where $k$ is the kissing number of the respective Euclidean space.

Improve this question
$\endgroup$
5
  • $\begingroup$ en.wikipedia.org/wiki/MST ... ? $\endgroup$
    – Tom De Medts
    Commented Apr 10, 2018 at 12:09
  • $\begingroup$ @TomDeMedts I think there is no ambiguity in the context of mathematics and especially for graphs. $\endgroup$
    – Manfred Weis
    Commented Apr 10, 2018 at 13:03
  • $\begingroup$ To add some context: such an MST is commonly called a (Euclidean) Steiner Tree. $\endgroup$
    – Peter Heinig
    Commented Apr 10, 2018 at 15:52
  • $\begingroup$ Probably, the results of this paper (especially Lemma 3) gives a negative answer to your question. am I missing something? $\endgroup$
    – Mahdi - Free Palestine
    Commented May 26, 2018 at 19:18
  • $\begingroup$ @Mahdi in the paper it is clearly stated, that the maximal MST degree is equal to the Hardwiger number, so you are right... Could you please turn your comment into an answer? $\endgroup$
    – Manfred Weis
    Commented May 26, 2018 at 19:48

1 Answer 1

Reset to default
1
$\begingroup$

The answer (maybe)1 is no. In the following paper,

Gabriel Robins and Jeffrey S. Salowe, On the maximum degree of minimum spanning trees. Proceedings of the tenth annual symposium on Computational Geometry (SCG '94), 250-258 (1994). PDF.

The authors proved that under the $L_p$ norm, the maximum vertex degree over all MSTs is equal to the kissing number of the corresponding unit ball;

1 I said 'maybe', since I have not checked the proof of the mentioned paper.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .