.png){kind=icon}
.png){kind=icon}
Return
Random Minimum Spanning Tree and Dense Graph Limits
.png){kind=icon}
PRE
AI
DOI：10.1002/rsa.70053.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A theorem of Frieze from 1985 asserts that the total length of the minimum spanning tree of the complete graph K-n whose edges get independent lengths from the distribution converges to Apery's constant in probability, as n -> infinity. We generalize this result to sequences of graphs G(n )that converge to a graphon W. Further, we allow the lengths k(W)of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total length of the minimum spanning tree is expressed in terms of a certain branching process defined on W, which was studied previously by Bollobas, Janson and Riordan in connection with the giant component in inhomogeneous random graphs.
Keywords:
dense graph limits
graphons
random minimum spanning tree
Journal
R
IF:
0
Papers:
29
Citations:
0