arXiv Analytics

Sign in

arXiv:1803.04958 [math.CO]AbstractReferencesReviewsResources

Spanning trees in randomly perturbed graphs

Felix Joos, Jaehoon Kim

Published 2018-03-13Version 1

A classical result of Koml\'os, S\'ark\"ozy and Szemer\'edi 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)}\leq \Delta\leq 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.

Related articles: Most relevant | Search more
arXiv:1101.5278 [math.CO] (Published 2011-01-27)
Nonseparating K4-subdivisions in graphs of minimum degree at least 4
arXiv:1408.5289 [math.CO] (Published 2014-08-22)
Graphs without proper subgraphs of minimum degree 3 and short cycles
arXiv:1107.4947 [math.CO] (Published 2011-07-25, updated 2011-08-08)
On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three