| Issue |
Europhys. Lett.
Volume 75, Number 1, July 2006
|
|
|---|---|---|
| Page(s) | 8 - 14 | |
| Section | General | |
| DOI | https://doi.org/10.1209/epl/i2006-10070-4 | |
| Published online | 31 May 2006 | |
Sudden emergence of q-regular subgraphs in random graphs
1
INFM-CNR, Dipartimento di Fisica, Politecnico di Torino Corso Duca degli Abruzzi 24, I-10129 Torino, Italy
2
Institute for Scientific Interchange - Viale Settimio Severo 65, I-10133 Torino, Italy
Received:
31
March
2006
Accepted:
5
May
2006
We investigate the computationally hard problem whether a random graph
of finite average vertex degree has an extensively large q-regular
subgraph, i.e., a subgraph with all vertices having degree equal
to q. We reformulate this problem as a constraint-satisfaction
problem, and solve it using the cavity method of statistical physics
at zero temperature. For 
, we find that the first large
q-regular subgraphs appear discontinuously at an average vertex
degree 3 and contain immediately about 
of all vertices in the graph. This transition is extremely close to
(but different from) the well-known 3-core percolation point
3. For 
, the q-regular subgraph
percolation threshold is found to coincide with that of the q-core.
PACS: 05.20.-y – Classical statistical mechanics / 02.50.-r – Probability theory, stochastic processes, and statistics / 89.20.-a – Interdisciplinary applications of physics
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.