{
  "id": "1210.5683",
  "version": "v1",
  "published": "2012-10-21T04:23:24.000Z",
  "updated": "2012-10-21T04:23:24.000Z",
  "title": "On the Existence of General Factors in Regular Graphs",
  "authors": [
    "Hongliang Lu",
    "David G. L. Wang",
    "Qinglin Yu"
  ],
  "comment": "10 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph, and $H\\colon V(G)\\to 2^\\mathbb{N}$ a set function associated with $G$. A spanning subgraph $F$ of $G$ is called an $H$-factor if the degree of any vertex $v$ in $F$ belongs to the set $H(v)$. This paper contains two results on the existence of $H$-factors in regular graphs. First, we construct an $r$-regular graph without some given $H^*$-factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lov\\'asz's characterization theorem on the existence of $(g, f)$-factors, we find a sharp condition for the existence of general $H$-factors in $\\{r, r+1\\}$-graphs, in terms of the maximum and minimum of $H$. The result reduces to Thomassen's theorem for the case that $H(v)$ consists of the same two consecutive integers for all vertices $v$, and to Tutte's theorem if the graph is regular in addition.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-10-21T04:23:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75"
    ],
    "keywords": [
      "regular graph",
      "general factors",
      "lovaszs characterization theorem",
      "paper contains",
      "set function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.5683L"
    }
  }
}