{
  "id": "math/0607234",
  "version": "v1",
  "published": "2006-07-10T00:09:45.000Z",
  "updated": "2006-07-10T00:09:45.000Z",
  "title": "On Hamiltonicity of {claw, net}-free graphs",
  "authors": [
    "Alexander Kelmans"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An st-path is a path with the end-vertices s and t. An s-path is a path with an end-vertex s. The results of this paper include necessary and sufficient conditions for a {claw, net}-free graph G with given two different vertices s, t and an edge e to have (1)a Hamiltonian s-path, (2) a Hamiltonian st-path, (3) a Hamiltonian s- and st-paths containing edge e when G has connectivity one, and (4) a Hamiltonian cycle containing e when G is 2-connected. These results imply that a connected {claw, net}-free graph has a Hamiltonian path and a 2-connected {claw, net}-free graph has a Hamiltonian cycle [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden Subgraphs and the Hamiltonian Theme, in The Theory and Application of Graphs (Kalamazoo, Mich., 1980$), Wiley, New York (1981) 297--316.] Our proofs of (1)-(4) are shorter than the proofs of their corollaries in [D. Duffus, R.J. Gould, M.S. Jacobson] and provide polynomial-time algorithms for solving the corresponding Hamiltonicity problems. Keywords: graph, claw, net, {claw, net}-free graph, Hamiltonian path, Hamiltonian cycle, polynomial-time algorithm.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-07-10T00:09:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10"
    ],
    "keywords": [
      "hamiltonian cycle",
      "hamiltonicity",
      "polynomial-time algorithm",
      "hamiltonian path",
      "hamiltonian s-path"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......7234K"
    }
  }
}