{
  "id": "0907.2490",
  "version": "v1",
  "published": "2009-07-15T05:19:44.000Z",
  "updated": "2009-07-15T05:19:44.000Z",
  "title": "A Lower Bound for the Circumference Involving Connectivity",
  "authors": [
    "Zh. G. Nikoghosyan"
  ],
  "comment": "32 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph, $C$ a longest cycle in $G$ and $\\overline{p}$, $\\overline{c}$ the lengths of a longest path and a longest cycle in $G\\backslash C$, respectively. Almost all lower bounds for the circumference base on a standard procedure: choose an initial cycle $C_0$ in $G$ and try to enlarge it via structures of $G\\backslash C_0$ and connections between $C_0$ and $G\\backslash C_0$ closely related to $\\overline{p}$, $\\overline{c}$ and connectivity $\\kappa$. Actually, each lower bound obtained in result of this procedure, somehow or is related to $\\kappa$, $\\overline{p}$, $\\overline{c}$ but in forms of various particular values of $\\kappa$, $\\overline{p}$, $\\overline{c}$ and the major problem is to involve these invariants into such bounds as parameters. In this paper we present a lower bound for the circumference involving $\\delta$, $\\kappa$ and $\\overline{c}$ and increasing with $\\delta$, $\\kappa$ and $\\overline{c}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-07-15T05:19:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C40"
    ],
    "keywords": [
      "lower bound",
      "connectivity",
      "longest cycle",
      "initial cycle",
      "longest path"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0907.2490N"
    }
  }
}