Spanning trees in randomly perturbed graphs

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/\log n)$ as a subgraph, and the bounds on the degree conditions are sharp. On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every $n$-vertex graph $G_{\alpha }$ with minimum degree at least $\alpha n$ for any fixed $\alpha >0$ and every $n$-vertex tree $T$ with bounded maximum degree, one can still find a copy of $T$ in $G_{\alpha }$ with high probability after adding $O(n)$ randomly-chosen edges to $G_{\alpha }$. We extend their results to trees with unbounded maximum degree. More precisely, for a given $n^{o(1)}\le \Delta \le cn/\log n$ and $\alpha >0$, we determine the precise number (up to a constant factor) of random edges that we need to add to an arbitrary $n$-vertex graph $G_{\alpha }$ with minimum degree $\alpha n$ in order to guarantee a copy of any fixed $n$-vertex tree $T$ with maximum degree at most~$\Delta$ with high probability.

41 pages

References in corpus (2)

• Adding random edges to dense graphs
• Hamiltonicity in randomly perturbed hypergraphs

Cited by in corpus (1)

• Tree decompositions of graphs without large bipartite holes