We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Spanning trees in randomly perturbed graphs.
- Authors
Joos, Felix; Kim, Jaehoon
- Abstract
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 O(n/logn). 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 no(1)≤Δ≤cn/logn 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 Δ.
- Subjects
SPANNING trees; RANDOM numbers; GEOMETRIC vertices; RANDOM graphs
- Publication
Random Structures & Algorithms, 2020, Vol 56, Issue 1, p169
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20886