Unicyclic components in random graphs

2004/03/18 by E. Ben-Naim, E Ben-Naim, P L Krapivsky +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Graph theory and applications #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.dis-nn #cond-mat.stat-mech #cs.DS #math.PR

paper · pdf · doi:10.1088/0305-4470/37/18/l01

published as J. Phys. A 37, L189 (2004) · 4 pages, 2 figures

arxiv created 2004/03/18 · openalex publication_date 2004/04/21 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

The distribution of unicyclic components in a random graph is obtained analytically. The number of unicyclic components of a given size approaches a self-similar form in the vicinity of the gelation transition. At the gelation point, this distribution decays algebraically, U_k ~ 1/(4k) for k>>1. As a result, the total number of unicyclic components grows logarithmically with the system size.

Cited by

• Percolation with multiple giant clusters
• Dynamics of random graphs with bounded degrees

Related

• Kinetic Theory of Random Graphs: from Paths to Cycles
• Cycles of given lengths in unicyclic components in sparse random graphs
• How to calculate the main characteristics of random graphs - a new approach
• The size of the giant component in random hypergraphs
• Kinetic Theory of Random Graphs