Expanders are universal for the class of all spanning trees

MaRDI QIDQ5743497zbMATH OpenFDO

Authors Daniel Johannsen, Michael Krivelevich, Wojciech Samotij

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095238

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• Expanders Are Universal for the Class of All Spanning Trees
• Embedding nearly-spanning bounded degree trees
• Sparse universal graphs for bounded‐degree graphs
• Large bounded degree trees in expanding graphs
• Spanning universality in random graphs

Cites work

• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 5764902 (Why is no real title available?)
• scientific article; zbMATH DE number 3733961 (Why is no real title available?)
• scientific article; zbMATH DE number 3750997 (Why is no real title available?)
• scientific article; zbMATH DE number 3613090 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A randomized embedding algorithm for trees
• Almost universal graphs
• An extension of the blow-up lemma to arrangeable graphs
• Combinatorial Games
• Embedding nearly-spanning bounded degree trees
• Embedding spanning trees in random graphs
• Expanding graphs contain all small trees
• Explicit sparse almost-universal graphs for \(\mathcal G (n, \frac kn)\)
• Hamilton cycles in highly connected and expanding graphs
• Hamilton cycles in random subgraphs of pseudo-random graphs
• Large bounded degree trees in expanding graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience of almost spanning trees in random graphs
• Maximal Flow Through a Network
• On Graphs Which Contain All Sparse Graphs
• On Universal Graphs for Spanning Trees
• On a combinatorial game
• On graphs which contain all small trees
• On the maximum degree in a random tree
• Pseudo-random graphs
• Random Trees in Random Graphs
• Random regular graphs of high degree
• Remarks on positional games. I
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Small universal graphs
• Spanning trees in dense graphs
• Sparse pseudo‐random graphs are Hamiltonian
• Sparse universal graphs
• Sparse universal graphs for bounded‐degree graphs
• The longest path in a random graph
• Tree embeddings
• Trees in sparse random graphs
• Uniform generation of random regular graphs of moderate degree
• Universal Graphs for Bounded-Degree Trees and Planar Graphs

Cited in

(4)

• Expanders Are Universal for the Class of All Spanning Trees
• Spanning trees in random graphs
• Expanders via random spanning trees
• Large bounded degree trees in expanding graphs

This page was built for publication: Expanders are universal for the class of all spanning trees

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