Sharp threshold for the appearance of certain spanning trees in random graphs

DOI10.1002/rsa.20472zbMath1255.05045OpenAlexW2091816879MaRDI QIDQ3145834

Dan Hefetz, Michael Krivelevich, Tibor Szabó

Publication date: 14 December 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20472

zbMATH Keywords

random graphssharp thresholdsspanning treestree-universality

Mathematics Subject Classification ID

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

Related Items (10)

Spanning Trees at the Connectivity Threshold ⋮ Spanning structures and universality in sparse hypergraphs ⋮ Color‐biased Hamilton cycles in random graphs ⋮ Fast embedding of spanning trees in biased maker-breaker games ⋮ Expanders Are Universal for the Class of All Spanning Trees ⋮ The threshold for combs in random graphs ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Spanning trees in random graphs ⋮ Unnamed Item ⋮ The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• Hamilton cycles in highly connected and expanding graphs
• Embedding nearly-spanning bounded degree trees
• Expanding graphs contain all small trees
• Trees in sparse random graphs
• The longest path in a random graph
• Large bounded degree trees in expanding graphs
• On the maximum degree in a random tree
• Tree embeddings
• Embedding Spanning Trees in Random Graphs
• Local resilience of almost spanning trees in random graphs
• Random Trees in Random Graphs
• Almost universal graphs

This page was built for publication: Sharp threshold for the appearance of certain spanning trees in random graphs