Random minimum length spanning trees in regular graphs

DOI10.1007/PL00009825zbMath0913.05085OpenAlexW2017052287WikidataQ57401554 ScholiaQ57401554MaRDI QIDQ1288911

Andrew Beveridge, Colin J. H. McDiarmid, Alan M. Frieze

Publication date: 18 May 1999

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009825

zbMATH Keywords

random graphsrandom spanning treesexpected minimum lengthregular connected graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items

A concentration inequality for the facility location problem ⋮ The largest hole in sparse random graphs ⋮ Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023 ⋮ Site percolation on pseudo‐random graphs ⋮ Supercritical site percolation on the hypercube: small components are small ⋮ Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes ⋮ Heavy and light paths and Hamilton cycles ⋮ Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes ⋮ On the Length of a Random Minimum Spanning Tree ⋮ Minimum Cost Matching in a Random Graph with Random Costs ⋮ Asymptotics in percolation on high‐girth expanders ⋮ A randomly weighted minimum spanning tree with a random cost constraint ⋮ On the Difference of Expected Lengths of Minimum Spanning Trees ⋮ On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph ⋮ Component structure of the vacant set induced by a random walk on a random graph ⋮ Geometry of the minimal spanning tree of a random 3-regular graph ⋮ Cross-Multiplicative Coalescent Processes and Applications ⋮ Successive shortest paths in complete graphs with random edge weights ⋮ The Effect of Adding Randomly Weighted Edges ⋮ On the rank of a random binary matrix ⋮ Expansion in supercritical random subgraphs of the hypercube and its consequences