Spanning Trees at the Connectivity Threshold

DOI10.1137/20M1380521MaRDI QIDQ5093583zbMATH OpenOpenAlexWikidataFDO

Authors Yahav Alon, Michael Krivelevich, Peleg Michaeli

Publication date 28 July 2022

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

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)

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Discrepancies of spanning trees and Hamilton cycles
• Hamiltonian circuits in random graphs
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Long paths and Hamiltonicity 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
• Random graphs.
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Spanning trees in random graphs
• The Evolution of Random Graphs
• The probabilistic method
• The threshold for combs in random graphs

Cited in

(1)

• scientific article; zbMATH DE number 5919760 (Why is no real title available?)

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)