Tail bound for the minimal spanning tree of a complete graph

Jeong Han Kim, Sungchul Lee

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


Suppose each edge of the complete graph Kn is assigned a random weight chosen independently and uniformly from the unit interval [0,1]. A minimal spanning tree is a spanning tree of Kn with the minimum weight. It is easy to show that such a tree is unique almost surely. This paper concerns the number Nn(α) of vertices of degree α in the minimal spanning tree of Kn. For a positive integer α, Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of Nn(α) is asymptotically γ(α)n, where γ(α) is a function of α given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Chernoff-type tail bound for Nn(α).

Original languageEnglish
Pages (from-to)425-430
Number of pages6
JournalStatistics and Probability Letters
Issue number4
Publication statusPublished - 2003 Oct 1

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Tail bound for the minimal spanning tree of a complete graph'. Together they form a unique fingerprint.

Cite this