Universality for bounded degree spanning trees in randomly perturbed graphs
Authors:
Open Access
- 7 April 2019
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 55 (4) , 854-864
Abstract
We solve a problem of Krivelevich, Kwan and Sudakov 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α on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.Keywords
All Related Versions
Funding Information
- EPSRC (EP/R00532X/1)
- FAPESP (2014/18641‐5, 2013/03447‐6, 2013/03447‐6)
- CNPq (310974/2013‐5, 311412/2018‐1, 459335/2014‐6)
- DFG (PE 2299/1‐1)
- CAPES (430/15, 57350402)
- DAAD (57391197)
This publication has 15 references indexed in Scilit:
- Embedding spanning bounded degree subgraphs in randomly perturbed graphsElectronic Notes in Discrete Mathematics, 2017
- Bounded-Degree Spanning Trees in Randomly Perturbed GraphsSIAM Journal on Discrete Mathematics, 2017
- Cycles and Matchings in Randomly Perturbed Digraphs and HypergraphsCombinatorics, Probability and Computing, 2016
- 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
- Tree embeddingsJournal of Graph Theory, 2001
- Threshold functionsCombinatorica, 1987
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976
- Some Theorems on Abstract GraphsProceedings of the London Mathematical Society, 1952