Bounded-degree spanning trees in randomly perturbed graphs

Krivelevich M, Kwan MA, Sudakov B. 2017. Bounded-degree spanning trees in randomly perturbed graphs. SIAM Journal on Discrete Mathematics. 31(1), 155–171.


Journal Article | Published | English

Scopus indexed
Author
Krivelevich, Michael; Kwan, Matthew AlanIST Austria; Sudakov, Benny
Abstract
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.
Publishing Year
Date Published
2017-01-12
Journal Title
SIAM Journal on Discrete Mathematics
Volume
31
Issue
1
Page
155-171
ISSN
eISSN
IST-REx-ID

Cite this

Krivelevich M, Kwan MA, Sudakov B. Bounded-degree spanning trees in randomly perturbed graphs. SIAM Journal on Discrete Mathematics. 2017;31(1):155-171. doi:10.1137/15m1032910
Krivelevich, M., Kwan, M. A., & Sudakov, B. (2017). Bounded-degree spanning trees in randomly perturbed graphs. SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/15m1032910
Krivelevich, Michael, Matthew Alan Kwan, and Benny Sudakov. “Bounded-Degree Spanning Trees in Randomly Perturbed Graphs.” SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics, 2017. https://doi.org/10.1137/15m1032910.
M. Krivelevich, M. A. Kwan, and B. Sudakov, “Bounded-degree spanning trees in randomly perturbed graphs,” SIAM Journal on Discrete Mathematics, vol. 31, no. 1. Society for Industrial & Applied Mathematics, pp. 155–171, 2017.
Krivelevich M, Kwan MA, Sudakov B. 2017. Bounded-degree spanning trees in randomly perturbed graphs. SIAM Journal on Discrete Mathematics. 31(1), 155–171.
Krivelevich, Michael, et al. “Bounded-Degree Spanning Trees in Randomly Perturbed Graphs.” SIAM Journal on Discrete Mathematics, vol. 31, no. 1, Society for Industrial & Applied Mathematics, 2017, pp. 155–71, doi:10.1137/15m1032910.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1507.07960

Search this title in

Google Scholar