Rainbow Hamiltonicity and the spectral radius

Yuke Zhang, Edwin R. van Dam

Published 2024-01-31, updated 2025-01-14Version 2

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.