Premium
Semi‐random graph process
Author(s) -
BenEliezer Omri,
Hefetz Dan,
Kronenberg Gal,
Parczyk Olaf,
Shikhelman Clara,
Stojaković Miloš
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20887
Subject(s) - multigraph , combinatorics , random regular graph , mathematics , random graph , null graph , vertex (graph theory) , discrete mathematics , graph , strength of a graph , regular graph , complement graph , line graph , voltage graph , pathwidth
We introduce and study a novel semi‐random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v . For various natural monotone increasing graph properties , we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies . Along the way, we show that the process is general enough to approximate (using suitable strategies) several well‐studied random graph models.