Premium
A variant of the Erdős–Rényi random graph process
Author(s) -
Logan Adam,
Molloy Mike,
Prałat Paweł
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22873
Subject(s) - combinatorics , mathematics , giant component , random graph , connected component , graph , discrete mathematics , wheel graph , graph power , line graph
Abstract We consider a natural variant of the Erdős–Rényi random graph process in whichk $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 roughlyn 1 ∕ 3${n}^{1\unicode{x02215}3}$ , wheren $n$ is the number of vertices.