Spanning Trees at the Connectivity Threshold

DOI10.1137/20M1380521zbMATH Open1493.05170arXiv2010.15519OpenAlexW3095274540WikidataQ114141811 ScholiaQ114141811MaRDI QIDQ5093583FDOQ5093583

Authors: Yahav Alon, Michael Krivelevich, Peleg Michaeli 

Publication date: 28 July 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We present an explicit connected spanning structure that appears in a random graph just above the connectivity threshold with high probability.

Full work available at URL: https://arxiv.org/abs/2010.15519

zbMATH Keywords

random graphconnectivityspanning tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Spanning trees in random graphs
• Random graphs.
• The probabilistic method
• Hamiltonian circuits in random graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• The Evolution of Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Introduction to Random Graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On the trace of random walks on random graphs
• Long paths and Hamiltonicity in random graphs
• Discrepancies of spanning trees and Hamilton cycles
• The threshold for combs in random graphs

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Spanning Trees at the Connectivity Threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093583)