Pith. sign in

Random minimum spanning tree and dense graph limits

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

A theorem of Frieze from 1985 asserts that the total weight of the minimum spanning tree of the complete graph $K_n$ whose edges get independent weights from the distribution $UNIFORM[0,1]$ converges to Ap\'ery's constant in probability, as $n\to\infty$. We generalize this result to sequences of graphs $G_n$ that converge to a graphon $W$. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight $\kappa(W)$ of the minimum spanning tree is expressed in terms of a certain branching process defined on $W$, which was studied previously by Bollob\'as, Janson and Riordan in connection with the giant component in inhomogeneous random graphs.

citation-role summary

background 1

citation-polarity summary

fields

math.PR 1

years

2024 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

citing papers explorer

Showing 1 of 1 citing paper.