{
  "id": "1510.09166",
  "version": "v1",
  "published": "2015-10-30T17:24:11.000Z",
  "updated": "2015-10-30T17:24:11.000Z",
  "title": "Long paths and cycles in random subgraphs of graphs with large minimum degree",
  "authors": [
    "Stefan Ehard",
    "Felix Joos"
  ],
  "comment": "13 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "For a graph $G$ and $p\\in [0,1]$, let $G_p$ arise from $G$ by deleting every edge mutually independently with probability $1-p$. The random graph model $(K_n)_p$ is certainly the most investigated random graph model and also known as the $G(n,p)$-model. We show that several results concerning the length of the longest path/cycle naturally translate to $G_p$ if $G$ is an arbitrary graph of minimum degree at least $n-1$. For a constant $c$, we show that asymptotically almost surely the length of the longest path is at least $(1-(1+\\epsilon(c))ce^{-c})n$ for some function $\\epsilon(c)\\to 0$ as $c\\to \\infty$, and the length of the longest cycle is a least $(1-O(c^{- \\frac{1}{5}}))n$. The first result is asymptotically best-possible. This extents several known results on the length of the longest path/cycle of a random graph in the $G(n,p)$-model.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-10-30T17:24:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "large minimum degree",
      "random subgraphs",
      "long paths",
      "random graph model",
      "longest path/cycle"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}