Spanning trees in randomly perturbed graphs
Spanning trees in randomly perturbed graphs
复制标题
随机扰动图中的生成树
DOI：
10.1002/rsa.20886
复制
发表时间：
--
影响因子：
1
通讯作者：
J. Kim
中科院分区：
文献类型：
--
作者：
F. Joos;J. Kim
Komlós、Sárközy 和 Szemerédi 的经典结果表明，最小度数至少为 (1/2 +o(1))n 的每个顶点图包含最大度数的每个顶点树。 Krivelevich、Kwan 和 Sudakov 证明，对于每个具有最小度数至少为 αn 的 n 顶点图 Gα，对于任何固定的 α> 0 和具有有界最大度的每个 n 顶点树 T，在向 Gα 添加 O(n) 条随机选择的边后，仍然可以高概率找到 TinGα 的副本。我们将后一个结果扩展到具有（本质上）无限最大度的树；对于给定且α> 0，我们确定需要添加到具有最小度数α的任意n顶点图的随机边的数量，最多为一个常数因子，以便以高概率保证最大度数最多为Δ的任何固定n顶点树的副本。
A classical result of Komlós, Sárközy, and Szemerédi states that everyn‐vertex graph with minimum degree at least (1/2 +o(1))ncontains everyn‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for everyn‐vertex graphGαwith minimum degree at leastαnfor any fixedα> 0 and everyn‐vertex treeTwith bounded maximum degree, one can still find a copy ofTinGαwith high probability after addingO(n) randomly chosen edges toGα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given andα> 0, we determine up to a constant factor the number of random edges that we need to add to an arbitraryn‐vertex graph with minimum degreeαnin order to guarantee with high probability a copy of any fixedn‐vertex tree with maximum degree at most Δ.
登录
查看更多内容
随机扰动超图中的哈密顿性
DOI：
10.1016/j.jctb.2019.12.005
发表时间：
2020
期刊：
Series B
影响因子：
--
作者：
Han, Jie;Zhao, Yi
通讯作者：
Zhao, Yi
DOI：
10.1137/15m1032910
发表时间：
2015
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Michael Krivelevich;Matthew Kwan;B. Sudakov
通讯作者：
B. Sudakov
影响因子：
1
作者：
Böttcher J
通讯作者：
Böttcher J
随机扰动密集图中的平铺
DOI：
10.1017/s0963548318000366
发表时间：
2018
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J
随机扰动有向图和超图中的循环和匹配
DOI：
10.1017/s0963548316000079
发表时间：
2015
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
Michael Krivelevich;Matthew Kwan;B. Sudakov
通讯作者：
B. Sudakov