Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T20:07:37.373Z Has data issue: false hasContentIssue false

Connectedness of graphs generated by a random d-process

Published online by Cambridge University Press:  09 April 2009

A. Ruciński
Affiliation:
Department of Discrete Mathematics, Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Matejki 48–49, 60–769 Poznań, Poland e-mail: rucinski@amu.edu.pl
N. C. Wormald
Affiliation:
Department of Mathematics, and Statistics, The University of Melbourne, VIC 3010, Australia e-mail: nick@ms.unimelb.edu.au
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Suppose that a graph process begins with n isolated 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 n → ∞, 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.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 2002