Rainbow Hamiltonian paths in graph collections under edge-size conditions
Abstract
Let G={G1,…,Gn−1} be a collection of not necessarily distinct graphs of order n on the same vertex set V. A path P with V(P)⊆ V is called \emph{rainbow} in G, if there exists an injection ϕ: E(P)→ [n−1] such that e∈ E(Gϕ(e)) for each e∈ E(P). In this paper, we show that if n≥3, e(Gi)> binomn−22+2 for each i∈[n−1] and Gj is connected for some j∈[n−1], then there exists a rainbow Hamiltonian path in G unless n=6 with G1=G2=…=G5≅ K2∨ 4K1, or n=8 with G1=G2=…=G7≅ K3∨ 5K1. This corrects Theorem 6 in [Graphs Combin., \textbf{41}(6)(2025), 119] and relaxes its hypothesis from requiring all Gi to be connected to only requiring that at least one Gi is connected, where i∈[n−1]. Moreover, we show that if n≥2 and e(Gi)≥ binomn−12 for each i∈[n−1], then G contains a rainbow Hamiltonian path unless G1=G2=…=Gn−1≅ Kn−1∪ K1, or n=4 with G1=G2=G3≅ K1,3. As a consequence, Theorem 2 of [Discrete Math., \textbf{347}(2024), 114128] follows immediately.
Related
- Edge and spectral conditions for rainbow pancyclicity in graph collections
- Edge and spectral conditions for rainbow bipancyclicity in bipartite graph collections
- Local Ore Conditions for Rainbow Pancyclicity and Vertex-Pancyclicity in Graph Systems
- Connectivity of the reconfiguration graph of Hamiltonian paths
- Local Fan-type obstructions and Ore-type conditions for rainbow Hamiltonicity in graph systems
BibTeX
@misc{zhang2026rainbow,
title = {{Rainbow Hamiltonian paths in graph collections under edge-size conditions}},
author = {Xiaoxue Zhang and Lihua You},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41203},
eprint = {2610.41203},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41203},
}
RIS
TY - UNPB
TI - Rainbow Hamiltonian paths in graph collections under edge-size conditions
AU - Xiaoxue Zhang
AU - Lihua You
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41203
UR - https://arxiv.org/abs/2610.41203
AB - Let G={G_1,…,G_n−1} be a collection of not necessarily distinct graphs of order n on the same vertex set V. A path P with V(P)⊆ V is called \emph{rainbow} in G, if there exists an injection ϕ: E(P)→ [n−1] such that e∈ E(G_ϕ(e)) for each e∈ E(P). In this paper, we show that if n≥3, e(G_i)> binomn−22+2 for each i∈[n−1] and G_j is connected for some j∈[n−1], then there exists a rainbow Hamiltonian path in G unless n=6 with G_1=G_2=…=G_5≅ K_2∨ 4K_1, or n=8 with G_1=G_2=…=G_7≅ K_3∨ 5K_1. This corrects Theorem 6 in [Graphs Combin., \textbf{41}(6)(2025), 119] and relaxes its hypothesis from requiring all G_i to be connected to only requiring that at least one G_i is connected, where i∈[n−1]. Moreover, we show that if n≥2 and e(G_i)≥ binomn−12 for each i∈[n−1], then G contains a rainbow Hamiltonian path unless G_1=G_2=…=G_n−1≅ K_n−1∪ K_1, or n=4 with G_1=G_2=G_3≅ K_1,3. As a consequence, Theorem 2 of [Discrete Math., \textbf{347}(2024), 114128] follows immediately.
ER -