z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here