The Distribution of Node Degree in Maximum Spanning Trees

We use Monte Carlo simulation to study the distribution of node degree in the Euclidean maximum spanning tree. Extrapolating from our experiments, we conjecture that, for uniformly distributed data, the asymptotic low-data-density probability of node degree k is proportional to k m 2 . This conjecture, if true, has implications for detecting outliers and testing random number generators.

Keywords:

• Maximum Spanning Tree
• Minimum Spanning Tree
• Monte Carlo Simulation
• Outlier
• Random Number Generation