Coja-Oghlan, Amin and Kang, Mihyun (2009) The evolution of the min–min random graph process. Discrete Mathematics, Vol.309 (No.13). pp. 4527-4544. doi:10.1016/j.disc.2009.02.015 ISSN 0012-365X.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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, View the MathML source 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 View the MathML source 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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	Discrete Mathematics
Publisher:	Elsevier BV
ISSN:	0012-365X
Official Date:	July 2009
Dates:	Date Event July 2009 Published
Volume:	Vol.309
Number:	No.13
Number of Pages:	18
Page Range:	pp. 4527-4544
DOI:	10.1016/j.disc.2009.02.015
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Deutsche Forschungsgemeinschaft
Grant number:	DFG Pr 296 / 7-3

Request changes or add full text files to a record

Repository staff actions (login required)

View Item