Bounded-degree spanning trees in randomly perturbed graphs
Krivelevich, Michael
Kwan, Matthew Alan
Sudakov, Benny
We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is c=c(α,Δ) such that if G is an n-vertex graph with minimum degree at least αn, and T is an n-vertex tree with maximum degree at most Δ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as n→∞ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest.
Society for Industrial & Applied Mathematics
2017
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/9590
Krivelevich M, Kwan MA, Sudakov B. Bounded-degree spanning trees in randomly perturbed graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2017;31(1):155-171. doi:<a href="https://doi.org/10.1137/15m1032910">10.1137/15m1032910</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1137/15m1032910
info:eu-repo/semantics/altIdentifier/issn/0895-4801
info:eu-repo/semantics/altIdentifier/issn/1095-7146
info:eu-repo/semantics/altIdentifier/arxiv/1507.07960
info:eu-repo/semantics/openAccess