A Bondy-type theorem for rainbow pancyclicity in graph systems

Source abstract

We establish a Hamiltonian-to-pancyclic analogue of Bondy's theorem for graph systems under an aggregate degree condition. Let $\G=(G_1,\ldots,G_n)$ be a graph system on a common $n$-vertex set $V$, and write $δ(v)=\min_{i\in[n]}d_{G_i}(v)$. If $\G$ contains a rainbow Hamilton cycle and $$\sum_{v\in V}δ(v)\ge \left\lceil\frac{n^2}{2}\right\rceil-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.