{
  "id": "2401.17845",
  "version": "v2",
  "published": "2024-01-31T14:04:34.000Z",
  "updated": "2025-01-14T05:00:38.000Z",
  "title": "Rainbow Hamiltonicity and the spectral radius",
  "authors": [
    "Yuke Zhang",
    "Edwin R. van Dam"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathcal{G}=\\{G_1,\\ldots,G_n \\}$ be a family of graphs of order $n$ with the same vertex set. A rainbow Hamiltonian cycle in $\\mathcal{G}$ is a cycle that visits each vertex precisely once such that any two edges belong to different graphs of $\\mathcal{G}$. We show that if each $G_i$ has more than $\\binom{n-1}{2}+1$ edges, then $\\mathcal{G}$ admits a rainbow Hamiltonian cycle and pose the problem of characterizing rainbow Hamiltonicity under the condition that all $G_i$ have at least $\\binom{n-1}{2}+1$ edges. Towards a solution of that problem, we give a sufficient condition for the existence of a rainbow Hamiltonian cycle in terms of the spectral radii of the graphs in $\\mathcal{G}$ and completely characterize the corresponding extremal graphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2025-01-14T05:00:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "spectral radius",
      "rainbow hamiltonian cycle",
      "characterizing rainbow hamiltonicity",
      "corresponding extremal graphs",
      "sufficient condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}