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.
Download full text files
Additional Services
| 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 |
