{
  "id": "1201.5707",
  "version": "v2",
  "published": "2012-01-27T06:27:56.000Z",
  "updated": "2013-11-13T00:07:44.000Z",
  "title": "Hamiltonicity of 3-arc graphs",
  "authors": [
    "Guangjun Xu",
    "Sanming Zhou"
  ],
  "comment": "in press Graphs and Combinatorics, 2013",
  "doi": "10.1007/s00373-013-1329-5",
  "categories": [
    "math.CO"
  ],
  "abstract": "An arc of a graph is an oriented edge and a 3-arc is a 4-tuple $(v,u,x,y)$ of vertices such that both $(v,u,x)$ and $(u,x,y)$ are paths of length two. The 3-arc graph of a graph $G$ is defined to have vertices the arcs of $G$ such that two arcs $uv, xy$ are adjacent if and only if $(v,u,x,y)$ is a 3-arc of $G$. In this paper we prove that any connected 3-arc graph is Hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are Hamiltonian. As a consequence we obtain that if a vertex-transitive graph is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three, then it is Hamiltonian. This confirms the well known conjecture, that all vertex-transitive graphs with finitely many exceptions are Hamiltonian, for a large family of vertex-transitive graphs. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-11-13T00:07:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C45",
      "05C76",
      "05C38"
    ],
    "keywords": [
      "vertex-transitive graph",
      "hamiltonicity",
      "hamiltonian",
      "minimum degree",
      "oriented edge"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}