Spanning trees in randomly perturbed graphs

Abstract: 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 / l o g 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_{a} l p h a

with minimum degree at least

a l p h a n

for any fixed

a l p h a > 0

and every

n

-vertex tree

T

with bounded maximum degree, one can still find a copy of

T

in

G_{a} l p h a

with high probability after adding

O (n)

randomly-chosen edges to

G_{a} l p h a

. We extend their results to trees with unbounded maximum degree. More precisely, for a given

n^{o (1)} l e q D e l t a l e q c n / l o g n

and

a l p h a > 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_{a} l p h a

with minimum degree

a l p h a n

in order to guarantee a copy of any fixed

n

-vertex tree

T

with maximum degree at most~

D e l t a

with high probability.

Recommendations

Cited In (33)

This page was built for publication: Spanning trees in randomly perturbed graphs