pipette
ESEspañol

A Bondy-type theorem for rainbow pancyclicity in graph systems

Ailian Chen, Liping Zhang

Preprint

In the authors' words

We establish a Hamiltonian-to-pancyclic analogue of Bondy's theorem for graph systems under an aggregate degree condition. Let be a graph system on a common -vertex set , and write . If contains a rainbow Hamilton cycle and \[ \sum_{v\in V}\delta(v)\ge \left\lceil\frac{n^2}{2}\right\rceil-1, \] then is rainbow pancyclic, unless is even and every member is the same balanced complete bipartite graph. For even 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 may depend on , and some vertices may have . 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. \noindentKeywords: graph system; rainbow cycle; pancyclicity; Hamilton cycle; extremal graph theory.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, September 24. arXiv. Preprint, not yet peer-reviewed.