{
  "id": "1811.07482",
  "version": "v2",
  "published": "2018-11-19T03:34:21.000Z",
  "updated": "2019-06-10T00:48:15.000Z",
  "title": "Minimum degree condition for a graph to be knitted",
  "authors": [
    "Runrun Liu",
    "Martin Rolek",
    "Gexin Yu"
  ],
  "comment": "4 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a positive integer $k$, a graph is $k$-knitted if for each $k$-subset $S$ of vertices, and every partition of $S$ into disjoint parts $S_1, \\ldots, S_t$ for some $t\\ge 1$, one can find disjoint connected subgraphs $C_1, \\ldots, C_t$ such that $C_i$ contains $S_i$ for each $i$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n/2+k/2-1$ when $n\\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $\\left\\lceil\\frac{k}{8}\\right\\rceil$-connected.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2019-06-10T00:48:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "minimum degree condition",
      "vertex graph",
      "disjoint connected subgraphs",
      "disjoint parts",
      "positive integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}