Spanning trees in randomly perturbed graphs
A classical result of Komlós, Sárközy, and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 + o(1))n contains every n-vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n-vertex graph Gα with minimum degree at least αn for any fixed...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2020
|
| In: |
Random structures & algorithms
Year: 2020, Volume: 56, Issue: 1, Pages: 169-219 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20886 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.20886 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20886 
|
| Author Notes: | Felix Joos, Jaehoon Kim |
| Summary: | A classical result of Komlós, Sárközy, and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 + o(1))n contains every n-vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n-vertex graph Gα with minimum degree at least αn for any fixed α > 0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in Gα with high probability after adding O(n) randomly chosen edges to Gα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n-vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n-vertex tree with maximum degree at most Δ. |
|---|---|
| Item Description: | Published on: 17 October 2019 Gesehen am 15.07.2022 |
| Physical Description: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20886 |