Volume 75, Number 1, July 2006
|Page(s)||8 - 14|
|Published online||31 May 2006|
Sudden emergence of q-regular subgraphs in random graphs
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
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.