J. Austral. Math. Soc.
72 (2002), 6785

Connectedness of graphs generated by a random dprocess

A. Rucinski
Department of Discrete Mathematics
Faculty of Mathematics and Computer Science
Adam Mickiewicz University
Matejki 4849
60769 Poznan
Poland
rucinski@amu.edu.pl


and

N. C. Wormald
Department of Mathematics and Statistics
The University of Melbourne
VIC 3010
Australia
nick@ms.unimelb.edu.au



Abstract

vertices, to which edges are added randomly one
by one so that the maximum degree of the induced
graph is always at most d.
In a previous article, the authors showed that as
, with probability tending to 1, the result of
this process is a dregular graph. This graph is shown to be
connected with probability asymptotic to 1.

Download the article in PDF format (size 152 Kb)


