The Infinite Locally Random Graph
Please always quote using this URN:urn:nbn:de:0296-matheon-2884
- We investigate properties of a certain countably infinite graph called the infinite locally random graph, written R_N. The graph R_N arises in the study of models for massive, self-organizing networks like the web-graph. We characterize the isomorphism type of R_N as the limit of a random process, and via a domination elimination ordering. We prove that R_N satisfies vertex deletion properties generalizing inexhaustibility. As is the case for the infinite random graph R, R_N has a universal automorphism group and endomorphism monoid. Unlike R, R_N isometrically embeds all finite graphs.
Author: | Manuel Bodirsky, Anthony Bonato |
---|---|
URN: | urn:nbn:de:0296-matheon-2884 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2005/05/11 |
Release Date: | 2005/10/31 |
Preprint Number: | 269 |