The evolution of the min-min random graph process |
| |
Authors: | Amin Coja-Oghlan |
| |
Institution: | a University of Edinburgh, School of Informatics, Edinburgh EH9 3JZ, UK b Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany |
| |
Abstract: | We study the following min-min random graph process G=(G0,G1,…): the initial state G0 is an empty graph on n vertices (n even). Further, GM+1 is obtained from GM by choosing a pair {v,w} of distinct vertices of minimum degree uniformly at random among all such pairs in GM and adding the edge {v,w}. The process may produce multiple edges. We show that GM is asymptotically almost surely disconnected if M≤n, and that for M=(1+t)n, constant, the probability that GM is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside the giant component of GM for M=(1+t)n. For constant we derive the precise limiting distribution of X. In addition, for n−1ln4n≤t=o(1) we show that tX converges to a gamma distribution. |
| |
Keywords: | Random graph Random graph process Connectedness Giant component |
本文献已被 ScienceDirect 等数据库收录! |
|