{
  "id": "0809.0702",
  "version": "v1",
  "published": "2008-09-03T20:16:46.000Z",
  "updated": "2008-09-03T20:16:46.000Z",
  "title": "Long cycles in graphs through fragments",
  "authors": [
    "Zh. G. Nikoghosyan"
  ],
  "comment": "32 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Four basic Dirac-type sufficient conditions for a graph $G$ to be hamiltonian are known involving order $n$, minimum degree $\\delta$, connectivity $\\kappa$ and independence number $\\alpha$ of $G$: (1) $\\delta \\geq n/2$ (Dirac); (2) $\\kappa \\geq 2$ and $\\delta \\geq (n+\\kappa)/3$ (by the author); (3) $\\kappa \\geq 2$ and $\\delta \\geq \\max\\lbrace (n+2)/3,\\alpha \\rbrace$ (Nash-Williams); (4) $\\kappa \\geq 3$ and $\\delta \\geq \\max\\lbrace (n+2\\kappa)/4,\\alpha \\rbrace$ (by the author). In this paper we prove the reverse version of (4) concerning the circumference $c$ of $G$ and completing the list of reverse versions of (1)-(4): (R1) if $\\kappa \\geq 2$, then $c\\geq\\min\\lbrace n,2\\delta\\rbrace$ (Dirac); (R2) if $\\kappa \\geq 3$, then $c\\geq\\min\\lbrace n,3\\delta -\\kappa\\rbrace$ (by the author); (R3) if $\\kappa\\geq 3$ and $\\delta\\geq \\alpha$, then $c\\geq\\min\\lbrace n,3\\delta-3\\rbrace$ (Voss and Zuluaga); (R4) if $\\kappa\\geq 4$ and $\\delta\\geq \\alpha$, then $c\\geq\\min\\lbrace n,4\\delta-2\\kappa\\rbrace$. To prove (R4), we present four more general results centered around a lower bound $c\\geq 4\\delta-2\\kappa$ under four alternative conditions in terms of fragments. A subset $X$ of $V(G)$ is called a fragment of $G$ if $N(X)$ is a minimum cut-set and $V(G)-(X\\cup N(X))\\neq\\emptyset$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-09-03T20:16:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C40"
    ],
    "keywords": [
      "long cycles",
      "basic dirac-type sufficient conditions",
      "reverse version",
      "minimum degree",
      "minimum cut-set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0809.0702N"
    }
  }
}