{
  "id": "cond-mat/0603819",
  "version": "v1",
  "published": "2006-03-30T15:18:57.000Z",
  "updated": "2006-03-30T15:18:57.000Z",
  "title": "Sudden emergence of q-regular subgraphs in random graphs",
  "authors": [
    "Marco Pretti",
    "Martin Weigt"
  ],
  "comment": "7 pages, 5 figures",
  "journal": "Europhys. Lett. 75, 8 (2006)",
  "doi": "10.1209/epl/i2006-10070-4",
  "categories": [
    "cond-mat.stat-mech",
    "cond-mat.dis-nn"
  ],
  "abstract": "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_\\reg{3} \\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_\\cor{3} \\simeq 3.3509$. For $q>3$, the $q$-regular subgraph percolation threshold is found to coincide with that of the $q$-core.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-03-30T15:18:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "q-regular subgraphs",
      "sudden emergence",
      "regular subgraph percolation threshold",
      "finite average vertex degree"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}