Europhys. Lett.
Volume 75, Number 1, July 2006
Page(s) 8 - 14
Section General
Published online 31 May 2006
Europhys. Lett., 75 (1), pp. 8-14 (2006)
DOI: 10.1209/epl/i2006-10070-4

Sudden emergence of q-regular subgraphs in random graphs

M. Pretti1 and M. Weigt2

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
published online 31 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 q=3, we find that the first large q-regular subgraphs appear discontinuously at an average vertex degree $c_{\mbox{\scriptsize${3}$ -reg}} \simeq 3.3546$ and contain immediately about $24\%$ of all vertices in the graph. This transition is extremely close to (but different from) the well-known 3-core percolation point $c_{\mbox{\scriptsize${3}$ -core}} \simeq 3.3509$. For q>3, the q-regular subgraph percolation threshold is found to coincide with that of the q-core.

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