J. Austral. Math. Soc.
72 (2002), 67-85
|
Connectedness of graphs generated by a random d-process
|
A. Rucinski
Department of Discrete Mathematics
Faculty of Mathematics and Computer Science
Adam Mickiewicz University
Matejki 48-49
60-769 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 d-regular graph. This graph is shown to be
connected with probability asymptotic to 1.
|
Download the article in PDF format (size 152 Kb)
|
|
|
|