Hostname: page-component-76fb5796d-5g6vh Total loading time: 0 Render date: 2024-04-27T04:53:06.283Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Star Processes

Published online by Cambridge University Press:  01 January 2000

H. D. ROBALEWSKA  and
N. C. WORMALD
H. D. ROBALEWSKA
Affiliation:
Department of Mathematics and Statistics, University of Melbourne, Parkville, VIC 3052, Australia (e-mail: hanna@ms.unimelb.edu.au, nick@ms.unimelb.edu.au)
N. C. WORMALD
Affiliation:
Department of Mathematics and Statistics, University of Melbourne, Parkville, VIC 3052, Australia (e-mail: hanna@ms.unimelb.edu.au, nick@ms.unimelb.edu.au)
Get access Rights & Permissions [Opens in a new window]

Abstract

A type of evolution of graphs with maximum vertex degree at most d is introduced. This evolution can start from any initial graph whose set of vertices of degree less than d is independent. The main concern is the regularity of graphs generated by this graph process when the initial graph has no edges. By analysis of the solutions of systems of differential equations it is shown that the final graph of this evolution is asymptotically almost surely a d-regular graph (subject to the usual parity condition).

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 9 , Issue 1 , January 2000 , pp. 33 - 43
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)