Metraipolis › archive › dc_1a6e321fc376
Edge and spectral conditions for rainbow pancyclicity in graph collections — arXiv:2609.23532
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23532
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T21:44:49.205Z
- SHA-256 of the archived text
22d2f201f0c36c3fba551f8bc4b4aecefe35ebad27f0a23e3e3578aa6cbaccd0- Stable URL of this page
https://metraipolis.com/documento/dc_1a6e321fc376
How to cite
Edge and spectral conditions for rainbow pancyclicity in graph collections — arXiv:2609.23532 — arXiv (en), https://arxiv.org/abs/2609.23532 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1a6e321fc376 (Metraipolis archive dc_1a6e321fc376, sha256 22d2f201f0c36c3fba551f8bc4b4aecefe35ebad27f0a23e3e3578aa6cbaccd0)
BibTeX
@misc{dc1a6e321fc376,
title = {Edge and spectral conditions for rainbow pancyclicity in graph collections — arXiv:2609.23532},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23532},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1a6e321fc376; sha256 22d2f201f0c36c3fba551f8bc4b4aecefe35ebad27f0a23e3e3578aa6cbaccd0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23532. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\phi\colon E(C)\to [n]$ such that $e\in E(G_{\phi(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 $\rho(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 $\rho(G_i)\ge n-2$ for each $i\in[n]$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.23532 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:26:41.118Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).