Edge and spectral conditions for rainbow pancyclicity in graph collections

Source abstract

Let $\mathbf{G}=\{G_1,\dots,G_{n}\}$ be a collection of not necessarily distinct $n$-vertex graphs with a common vertex set $V$. A cycle $C$ with $V(C)\subseteq V$ and $|E(C)|\leq n$ is called \emph{rainbow} in $\mathbf{G}$, if there exists an injection $φ\colon E(C)\to [n]$ such that $e\in E(G_{φ(e)})$ for each $e\in E(C)$. The graph collection $\mathbf{G}$ is said to be \emph{rainbow pancyclic} if it contains a rainbow cycle of every length from 3 to $n$. In this paper, we show that if $e(G_i)\ge \binom{n-1}{2}+1$ for each $i\in[n]$ with $n\ge 3$, then $\mathbf{G}$ is rainbow pancyclic, apart from three explicitly described exceptional graph collections. This answers Problem $1$ of [Discrete Math., \textbf {348}(2025), 114600] and strengthens the result from rainbow Hamiltonicity to rainbow pancyclicity. As a consequence, we obtain that if $ρ(G_i)>n-2$ for each $i\in[n]$, then $\mathbf{G}$ is rainbow pancyclic unless $G_1=G_2=\dots=G_n\cong K_1\vee(K_{n-2}\cup K_1)$, which improves Theorem $5$ of [Discrete Math., \textbf {348}(2025), 114600]. We also characterize all graph collections that are not rainbow pancyclic under the condition $ρ(G_i)\ge n-2$ for each $i\in[n]$.