{
  "id": "1702.05873",
  "version": "v1",
  "published": "2017-02-20T06:30:18.000Z",
  "updated": "2017-02-20T06:30:18.000Z",
  "title": "Characterization of 1-Tough Graphs using Factors",
  "authors": [
    "M. Kano",
    "H. Lu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a graph $G$, let $odd(G)$ and $\\omega(G)$ denote the number of odd components and the number of components of $G$, respectively. Then it is well-known that $G$ has a 1-factor if and only if $odd(G-S)\\le |S|$ for all $S\\subset V(G)$. Also it is clear that $odd(G-S) \\le \\omega(G-S)$. In this paper we characterize a 1-tough graph $G$, which satisfies $\\omega(G-S) \\le |S|$ for all $\\emptyset \\ne S \\subset V(G)$, using an $H$-factor of a set-valued function $H:V(G) \\to \\{ \\{1\\}, \\{0,2,4, \\ldots\\} \\}$. Moreover, we generalize this characterization to a graph that satisfies $\\omega(G-S) \\le f(S)$ for all $\\emptyset \\ne S \\subset V(G)$, where $f:V(G) \\to \\{1,3,5, \\ldots\\}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-20T06:30:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "characterization",
      "odd components",
      "set-valued function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}