Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-16T15:20:05.683Z Has data issue: false hasContentIssue false
  • English
  • Français

Connectedness of graphs generated by a random d-process

Part of: Special processes Graph theory

Published online by Cambridge University Press:  09 April 2009

A. Ruciński  and
N. C. Wormald
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: [email protected]
N. C. Wormald
Affiliation:
Department of Mathematics, and Statistics, The University of Melbourne, VIC 3010, Australia e-mail: [email protected]
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.

MSC classification

Secondary: 05C80: Random graphs 60K99: None of the above, but in this section
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 72 , Issue 1 , February 2002 , pp. 67 - 86
Copyright
Copyright © Australian Mathematical Society 2002

References

[1]Bollobás, B., Random graphs (Academic Press, London, 1985).Google Scholar
[2]Erdós, P. and Rényi, A., ‘On random graphs I’, Publ. Math. Debrecen 6 (1959), 290–297.CrossRefGoogle Scholar
[3]McDiamid, C., ‘On the method of bounded differences’, in: Surveys in combinatorics 1989 (ed. Siemons, J.) (Cambridge University Press, Cambridge, 1989), pp. 148–188.CrossRefGoogle Scholar
[4]Ruciński, A. and Wormald, N. C., ‘Random graph processes with degree restrictions’, Combin. Probab. Comput. 1 (1992), 169–180.CrossRefGoogle Scholar
[5]Shamir, E. and Spencer, J., ‘Sharp concentration of the chromatic number on random graphs G n p’, Combinatorica 7 (1987), 121–129.CrossRefGoogle Scholar
[6]Telcs, A., Wormald, N. C. and Zhou, S., ‘Hamiltonicity of random 2-processes’, (in preparation).Google Scholar
[7]Wormald, N. C., ‘Differential equations for random processes and random graphs’, Ann. Appl. Probab. 5 (1995), 1217–1235.CrossRefGoogle Scholar