A variant of the Erdos-Renyi random graph process

被引：1

作者：

Logan, Adam ^{[1
]}

Molloy, Mike ^{[2
]}

Pralat, Pawel ^{[3
]}

机构：

[1] Tutte Inst Math & Comp, Ottawa, ON, Canada

[2] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada

[3] Toronto Metropolitan Univ, Dept Math, 350 Victoria St, Toronto, ON M5B 2K3, Canada

来源：

JOURNAL OF GRAPH THEORY | 2023年 / 102卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

constrained random graph processes; giant component; random graphs;

D O I：

10.1002/jgt.22873

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider a natural variant of the Erdos-Renyi random graph process in which k vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the multiway cut problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition for the appearance of the giant component occurs when the number of special vertices is roughly n(1/3), where n is the number of vertices.

引用

页码：322 / 345

页数：24

共 20 条

[1] Aldous, 1990, RANDOM STRUCT ALGOR, V1, P383, DOI DOI 10.1002/RSA.3240010402
[2] Dynamic concentration of the triangle-free process
Bohman, Tom
Keevash, Peter
[J]. RANDOM STRUCTURES & ALGORITHMS, 2021, 58 (02) : 221 - 293
[3] The triangle-free process
Bohman, Tom
[J]. ADVANCES IN MATHEMATICS, 2009, 221 (05) : 1653 - 1677
[4] Bollob?s, 2000, ELECTRON J COMB, V7, pR18, DOI DOI 10.37236/1496
[5] Bollobas B., 2001, Cambridge Studies in Advanced Mathematics, DOI DOI 10.1017/CBO9780511814068
[6] Darling D.G., 2019, MATH COMB, V48
[7] ON THE SIZE OF A RANDOM MAXIMAL GRAPH
ERDOS, P
SUEN, S
WINKLER, P
[J]. RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (2-3) : 309 - 318
[8] Erds P., 1959, Publ. Math. Debrecen, V6, P290, DOI [10.5486/PMD.1959.6.3-4.12, DOI 10.5486/PMD.1959.6.3-4.12]
[9] FRIEZE A., 2015, INTRO RANDOM GRAPHS
[10] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

← 1 2 →