Dynamic random graphs with vertex removal
From MaRDI portal
Publication:6404641
arXiv2207.05046MaRDI QIDQ6404641FDOQ6404641
Authors: J. Díaz, Lyuben Lichev, Bas Lodewijks 
Publication date: 11 July 2022
Abstract: We introduce and analyse a Dynamic Random Graph with Vertex Removal (DRGVR) defined as follows. At every step, with probability a new vertex is introduced, and with probability a vertex, chosen uniformly at random among the present ones (if any), is removed from the graph together with all edges adjacent to it. In the former case, the new vertex connects by an edge to every other vertex with probability proportional to the number of vertices already present. We prove that the DRGVR converges to a local limit and determine this limit. Moreover, we analyse its component structure and distinguish a subcritical and a supercritical regime with respect to the existence of a giant component. As a byproduct of this analysis, we obtain upper and lower bounds for the critical parameter. Furthermore, we provide precise expression of the maximum degree (as well as in- and out-degree for a natural orientation of the DRGVR). Several concentration and stability results complete the study.
This page was built for publication: Dynamic random graphs with vertex removal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404641)
