A Bondy-type theorem for rainbow pancyclicity in graph systems
Abstract
We establish a Hamiltonian-to-pancyclic analogue of Bondy's theorem for graph systems under an aggregate degree condition. Let G=(G1,…,Gn) be a graph system on a common n-vertex set V, and write δ(v)=mini∈[n]dGi(v). If G contains a rainbow Hamilton cycle and ∑v∈ Vδ(v)≥ ⌈n2/2⌉−1, then G is rainbow pancyclic, unless n is even and every member is the same balanced complete bipartite graph. For even n the threshold is exact at the integer level. Unlike the usual transversal Dirac- or Ore-type hypotheses, our condition is not layerwise: the member attaining δ(v) may depend on v, and some vertices may have δ(v)<n/2. Relative to a fixed rainbow Hamilton cycle, we count shortcuts whose colors are released by the Hamilton arcs they replace. A missing cycle length forces complementary shortcut supports to cross-intersect. A counting gap settles even shortening, while equality or near equality in odd shortening yields a distance-two exchange whose orbits force the balanced bipartite obstruction. At the lower integer threshold an exact defect identity shows that only one or two units of slack are available. \noindent\textbf{Keywords:} graph system; rainbow cycle; pancyclicity; Hamilton cycle; extremal graph theory.
Related
- Local Ore Conditions for Rainbow Pancyclicity and Vertex-Pancyclicity in Graph Systems
- Edge and spectral conditions for rainbow pancyclicity in graph collections
- Local Fan-type obstructions and Ore-type conditions for rainbow Hamiltonicity in graph systems
- A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
- A rainbow partition theorem for trees and connected maximin share allocations of chores
BibTeX
@misc{chen2026bondytype,
title = {{A Bondy-type theorem for rainbow pancyclicity in graph systems}},
author = {Ailian Chen and Liping Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27692},
eprint = {2609.27692},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27692},
}
RIS
TY - UNPB
TI - A Bondy-type theorem for rainbow pancyclicity in graph systems
AU - Ailian Chen
AU - Liping Zhang
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27692
UR - https://arxiv.org/abs/2609.27692
AB - We establish a Hamiltonian-to-pancyclic analogue of Bondy's theorem for graph systems under an aggregate degree condition. Let G=(G_1,…,G_n) be a graph system on a common n-vertex set V, and write δ(v)=min_i∈[n]d_G_i(v). If G contains a rainbow Hamilton cycle and ∑_v∈ Vδ(v)≥ ⌈n^2/2⌉−1, then G is rainbow pancyclic, unless n is even and every member is the same balanced complete bipartite graph. For even n the threshold is exact at the integer level. Unlike the usual transversal Dirac- or Ore-type hypotheses, our condition is not layerwise: the member attaining δ(v) may depend on v, and some vertices may have δ(v)<n/2. Relative to a fixed rainbow Hamilton cycle, we count shortcuts whose colors are released by the Hamilton arcs they replace. A missing cycle length forces complementary shortcut supports to cross-intersect. A counting gap settles even shortening, while equality or near equality in odd shortening yields a distance-two exchange whose orbits force the balanced bipartite obstruction. At the lower integer threshold an exact defect identity shows that only one or two units of slack are available. \noindent\textbf{Keywords:} graph system; rainbow cycle; pancyclicity; Hamilton cycle; extremal graph theory.
ER -