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

^*此作品的通讯作者

科研成果: 期刊稿件 › 文章 › 同行评审

33 引用（Scopus）

摘要

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 Δ.

源语言	英语
页（从-至）	854-864
页数	11
期刊	Random Structures and Algorithms
卷	55
期	4
DOI	https://doi.org/10.1002/rsa.20850
出版状态	已出版 - 1 12月 2019
已对外发布	是

访问文件

10.1002/rsa.20850

其它文件与链接

链接到 Scopus 的出版物

引用此

Böttcher, J., Han, J., Kohayakawa, Y., Montgomery, R., Parczyk, O., & Person, Y. (2019). Universality for bounded degree spanning trees in randomly perturbed graphs. Random Structures and Algorithms, 55(4), 854-864. https://doi.org/10.1002/rsa.20850

@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

摘要

访问文件

其它文件与链接

指纹

引用此