Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T04:49:28.036Z Has data issue: false hasContentIssue false

A preferential attachment process approaching the Rado graph

Part of:Graph theory

Published online by Cambridge University Press:  27 February 2020

Richard Elwes*
Affiliation:
School of Mathematics, University of Leeds, UK (r.h.elwes@leeds.ac.uk)
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.

We consider a simple preferential attachment graph process, which begins with a finite graph and in which a new (t + 1)st vertex is added at each subsequent time step t that is connected to each previous vertex u ≤ t with probability du(t)/t, where du(t) is the degree of u at time t. We analyse the graph obtained as the infinite limit of this process, and we show that, as long as the initial finite graph is neither edgeless nor complete, with probability 1 the outcome will be a copy of the Rado graph augmented with a finite number of either isolated or universal vertices.

MSC classification

Information

Type
Research Article
Copyright
Copyright © The Author(s), 2020. Published by Cambridge University Press