Universality for bounded degree spanning trees in randomly perturbed graphs
Authors:
- Julia BöttcherJBJulia Böttcher
- Jie HanJHJie Han
- Yoshiharu KohayakawaYKYoshiharu Kohayakawa
- Richard MontgomeryRMRichard Montgomery
- Olaf ParczykOPOlaf Parczyk
- Yury PersonYPYury Person
Preprint
Abstract
We solve a problem of Krivelevich, Kwan and Sudakov [SIAM Journal on Discrete Mathematics 31 (2017), 155-171] concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph $G_\alpha$ on $n$ vertices with $\delta(G_\alpha)\ge \alpha n$ for $\alpha>0$ and we add to it the binomial random graph $G(n,C/n)$, then with high probability the graph $G_\alpha\cup G(n,C/n)$ contains copies of all spanning trees with maximum degree at most $\Delta$ simultaneously, where $C$ depends only on $\alpha$ and $\Delta$.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Hamiltonicity in randomly perturbed hypergraphsJournal of Combinatorial Theory, Series B, 2020
- Spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Powers of tight Hamilton cycles in randomly perturbed hypergraphsRandom Structures & Algorithms, 2019
- Hamilton $\ell$-Cycles in Randomly Perturbed HypergraphsThe Electronic Journal of Combinatorics, 2018
- Cycles and Matchings in Randomly Perturbed Digraphs and HypergraphsCombinatorics, Probability and Computing, 2016
- Large Bounded Degree Trees in Expanding GraphsThe Electronic Journal of Combinatorics, 2010
- Embedding nearly-spanning bounded degree treesCombinatorica, 2007
- How many random edges make a dense graph hamiltonian?Random Structures & Algorithms, 2002
- Spanning Trees in Dense GraphsCombinatorics, Probability and Computing, 2001