Simple evolving random graphs.

Abstract

We study random graphs densifying by adding edges. In each step, two vertices are randomly chosen, and an edge between these vertices is created if the vertices belong to trees. An edge is added with probability p if only one vertex belongs to a tree and an attempt fails otherwise. Simple random graphs generated by this procedure contain only trees and unicycles. In the thermodynamic limit, the fraction of vertices in unicycles exhibits a phase transition resembling a percolation transition in classical random graphs. In contrast to classical random graphs, where a giant component born at the transition point eventually engulfs all finite components and densifies forever, the evolution of simple random graphs freezes when trees disappear. We quantify simple random graphs in the supercritical phase and the properties of the frozen state.