Local Fan-type obstructions and Ore-type conditions for rainbow Hamiltonicity in graph systems
Abstract
Let G=(G1,...,Gn) be a graph system on a common n-vertex set V. For v∈ V, set δ(v)=mini∈[n]dGi(v), E∩=⋂i=1n E(Gi), and let dc(u,v) denote the length of a shortest rainbow u--v path. We study Hamiltonicity conditions imposed only on pairs at small rainbow distance. Suppose that every Gi is $2$-connected and that δ(u),δ(v)<n/2, dc(u,v)≤2 Longrightarrow uv∈ E∩. Our main result shows that any system satisfying this local Fan-type condition but containing no rainbow Hamilton cycle must satisfy E∩=∅, ∑v∈ Vδ(v)≤(n2−1)/2. Consequently, either E∩≠∅ or ∑v∈ Vδ(v)≥⌈ n2/2⌉ guarantees a rainbow Hamilton cycle. We further prove that the local Ore-type condition δ(u)+δ(v)<n, dc(u,v)≤2 Longrightarrow uv∈ E∩ already forces a rainbow Hamilton cycle. Along the way, the Fan-type hypothesis yields a rainbow Hamilton path and a rainbow (n−1)-cycle. For diagonal systems, our conditions reduce to the classical Fan and local Ore conditions. The proofs combine rainbow rotation--extension with a double-counting argument in an auxiliary digraph. Keywords: graph system; rainbow Hamilton cycle; rainbow distance; Fan-type condition; Ore-type condition; rotation--extension.
Related
- Local Ore Conditions for Rainbow Pancyclicity and Vertex-Pancyclicity in Graph Systems
- Rainbow Berge Hamiltonicity in edge-colored random k-uniform hypergraphs
- Signless Laplacian spectral conditions for rainbow matchings in a collection of bipartite graphs
- Edge and spectral conditions for rainbow pancyclicity in graph collections
- Rainbow Hamiltonian paths in graph collections under edge-size conditions
BibTeX
@misc{chen2026local,
title = {{Local Fan-type obstructions and Ore-type conditions for rainbow Hamiltonicity in graph systems}},
author = {Ailian Chen and Hao Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13977},
eprint = {2610.13977},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13977},
}
RIS
TY - UNPB
TI - Local Fan-type obstructions and Ore-type conditions for rainbow Hamiltonicity in graph systems
AU - Ailian Chen
AU - Hao Chen
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.13977
UR - https://arxiv.org/abs/2610.13977
AB - Let G=(G_1,...,G_n) be a graph system on a common n-vertex set V. For v∈ V, set δ(v)=min_i∈[n]d_G_i(v), E_∩=⋂_i=1^n E(G_i), and let d^c(u,v) denote the length of a shortest rainbow u--v path. We study Hamiltonicity conditions imposed only on pairs at small rainbow distance. Suppose that every G_i is $2$-connected and that δ(u),δ(v)<n/2, d^c(u,v)≤2 Longrightarrow uv∈ E_∩. Our main result shows that any system satisfying this local Fan-type condition but containing no rainbow Hamilton cycle must satisfy E_∩=∅, ∑_v∈ Vδ(v)≤(n^2−1)/2. Consequently, either E_∩≠∅ or ∑_v∈ Vδ(v)≥⌈ n^2/2⌉ guarantees a rainbow Hamilton cycle. We further prove that the local Ore-type condition δ(u)+δ(v)<n, d^c(u,v)≤2 Longrightarrow uv∈ E_∩ already forces a rainbow Hamilton cycle. Along the way, the Fan-type hypothesis yields a rainbow Hamilton path and a rainbow (n−1)-cycle. For diagonal systems, our conditions reduce to the classical Fan and local Ore conditions. The proofs combine rainbow rotation--extension with a double-counting argument in an auxiliary digraph. Keywords: graph system; rainbow Hamilton cycle; rainbow distance; Fan-type condition; Ore-type condition; rotation--extension.
ER -