Expanders are universal for the class of all spanning trees
zbMATH Open1423.05087MaRDI QIDQ5743497FDOQ5743497
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
Recommendations
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)
Cites Work
- Maximal Flow Through a Network
- Title not available (Why is that?)
- Sparse pseudo‐random graphs are Hamiltonian
- Trees in sparse random graphs
- Tree embeddings
- Embedding nearly-spanning bounded degree trees
- Expanding graphs contain all small trees
- Large bounded degree trees in expanding graphs
- On the maximum degree in a random tree
- Remarks on positional games. I
- Combinatorial Games
- On a combinatorial game
- Random regular graphs of high degree
- Title not available (Why is that?)
- Pseudo-random graphs
- Sparse universal graphs
- Embedding spanning trees in random graphs
- Local resilience of almost spanning trees in random graphs
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
- On Graphs Which Contain All Sparse Graphs
- On Universal Graphs for Spanning Trees
- Sparse universal graphs for bounded‐degree graphs
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Uniform generation of random regular graphs of moderate degree
- Hamilton cycles in random subgraphs of pseudo-random graphs
- An extension of the blow-up lemma to arrangeable graphs
- The longest path in a random graph
- Hamilton cycles in highly connected and expanding graphs
- Almost universal graphs
- Sharp threshold for the appearance of certain spanning trees in random graphs
- A randomized embedding algorithm for trees
- On graphs which contain all small trees
- Explicit sparse almost-universal graphs for \(\mathcal G (n, \frac kn)\)
- Small universal graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Spanning trees in dense graphs
- Title not available (Why is that?)
- Random Trees in Random Graphs
- Title not available (Why is that?)
Cited In (4)
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)
