Universality for bounded degree spanning trees in randomly perturbed graphs

Julia Böttcher; Jie Han; Yoshiharu Kohayakawa; Richard Montgomery; Olaf Parczyk; Yury Person

doi:10.1002/rsa.20850

Universality for bounded degree spanning trees in randomly perturbed graphs

Julia Böttcher^*, Jie Han, Yoshiharu Kohayakawa, Richard Montgomery, Olaf Parczyk, Yury Person

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

32 Citations (Scopus)

Abstract

We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G_α on n vertices with δ(G_α) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph G_α∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.

Original language	English
Pages (from-to)	854-864
Number of pages	11
Journal	Random Structures and Algorithms
Volume	55
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20850
Publication status	Published - 1 Dec 2019
Externally published	Yes

Keywords

perturbed graphs
random graphs
spanning trees
universality

Access to Document

10.1002/rsa.20850

Cite this

@article{c6220f90069242d880a7f65b0194edf8,

title = "Universality for bounded degree spanning trees in randomly perturbed graphs",

abstract = "We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph Gα on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.",

keywords = "perturbed graphs, random graphs, spanning trees, universality",

author = "Julia B{\"o}ttcher and Jie Han and Yoshiharu Kohayakawa and Richard Montgomery and Olaf Parczyk and Yury Person",

note = "Publisher Copyright: {\textcopyright} 2019 The Authors. Random Structures and Algorithms published by Wiley Periodicals, Inc.",

year = "2019",

month = dec,

day = "1",

doi = "10.1002/rsa.20850",

language = "English",

volume = "55",

pages = "854--864",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - Universality for bounded degree spanning trees in randomly perturbed graphs

AU - Böttcher, Julia

AU - Han, Jie

AU - Kohayakawa, Yoshiharu

AU - Montgomery, Richard

AU - Parczyk, Olaf

AU - Person, Yury

PY - 2019/12/1

Y1 - 2019/12/1

N2 - We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph Gα on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.

AB - We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph Gα on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.

KW - perturbed graphs

KW - random graphs

KW - spanning trees

KW - universality

UR - http://www.scopus.com/inward/record.url?scp=85063990016&partnerID=8YFLogxK

U2 - 10.1002/rsa.20850

DO - 10.1002/rsa.20850

M3 - Article

AN - SCOPUS:85063990016

SN - 1042-9832

VL - 55

SP - 854

EP - 864

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

Universality for bounded degree spanning trees in randomly perturbed graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this