{
  "id": "2408.04618",
  "version": "v1",
  "published": "2024-08-08T17:48:13.000Z",
  "updated": "2024-08-08T17:48:13.000Z",
  "title": "Longest cycles in vertex-transitive and highly connected graphs",
  "authors": [
    "Carla Groenland",
    "Sean Longbrake",
    "Raphael Steiner",
    "Jérémie Turcotte",
    "Liana Yepremyan"
  ],
  "comment": "13 pages, 3 figures. Code available at https://github.com/tjeremie/Long-cycles",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We present progress on two old conjectures about longest cycles in graphs. The first conjecture, due to Thomassen from 1978, states that apart from a finite number of exceptions, all connected vertex-transitive graphs contain a Hamiltonian cycle. The second conjecture, due to Smith from 1984, states that for $r\\ge 2$ in every $r$-connected graph any two longest cycles intersect in at least $r$ vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph which can be used to improve the best known bounds towards both of the aforementioned conjectures: First, we show that every connected vertex-transitive graph on $n\\geq 3$ vertices contains a cycle of length at least $\\Omega(n^{13/21})$, improving on $\\Omega(n^{3/5})$ from [De Vos, arXiv:2302:04255, 2023]. Second, we show that in every $r$-connected graph with $r\\geq 2$, any two longest cycles meet in at least $\\Omega(r^{5/8})$ vertices, improving on $\\Omega(r^{3/5})$ from [Chen, Faudree and Gould, J. Combin. Theory, Ser.~ B, 1998]. Our proof combines combinatorial arguments, computer-search and linear programming.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-08T17:48:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C45",
      "05C60",
      "68V05"
    ],
    "keywords": [
      "highly connected graphs",
      "longest cycles intersect",
      "longest cycles meet",
      "second conjecture",
      "hamiltonian cycle"
    ],
    "tags": [
      "github project"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}