Premium
Random minimal spanning tree and percolation on the N ‐cube
Author(s) -
Penrose Mathew D.
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199801)12:1<63::aid-rsa4>3.0.co;2-r
Subject(s) - combinatorics , spanning tree , mathematics , cube (algebra) , random graph , percolation (cognitive psychology) , enhanced data rates for gsm evolution , minimum spanning tree , weight distribution , graph , tree (set theory) , discrete mathematics , physics , computer science , telecommunications , neuroscience , biology , thermodynamics
The N ‐cube is a graph with 2 N vertices and N 2 N −1 edges. Suppose independent uniform random edge weights are assigned and let T be the spanning tree of minimal (total) weight. Then the weight of T is asymptotic to N −1 2 N ∑ ∞ i =1 i −3 as N →∞. Asymptotics are also given for the local structure of T and for the distribution of its k th largest edge weight, k fixed. © 1998 John Wiley & Sons, Inc. Random Struct. Alg. , 12, 63–82, 1998