https://doi.org/10.1007/s10051-001-8683-4
Core percolation in random graphs: a critical phenomena analysis
Service de Physique Théorique, CEA Saclay, 91191 Gif-sur-Yvette, France
Corresponding authors: a bauer@spht.saclay.cea.fr - b golinelli@spht.saclay.cea.fr
Received:
31
January
2001
Revised:
26
June
2001
Published online: 15 December 2001
We study both numerically and analytically what happens to a random graph
of average connectivity α when its leaves and their neighbors are
removed iteratively up to the point when no leaf remains. The remnant is
made of isolated vertices plus an induced subgraph we call the core.
In the thermodynamic limit of an infinite random graph, we compute
analytically the dynamics of leaf removal, the number of isolated vertices
and the number of vertices and edges in the core. We show that a second
order phase transition occurs at 
: below the
transition, the core is small but above the transition, it occupies a
finite fraction of the initial graph. The finite size scaling properties
are then studied numerically in detail in the critical region, and we
propose a consistent set of critical exponents, which does not coincide
with the set of standard percolation exponents for this model. We clarify
several aspects in combinatorial optimization and spectral properties of
the adjacency matrix of random graphs.
PACS: 02.10.-v – Logic, set theory, and algebra / 02.50.-r – Probability theory, stochastic processes, and statistics / 64.60.Ak – Renormalization-group, fractal, and percolation studies of phase transitions / 64.60.Fr – Equilibrium properties near critical points, critical exponents
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2001
