March 3, 2026Open Access

Power-of-Two Cycles in Cubic Bipartite Vertex-Transitive Graphs of Girth Six

Key Points

Every cubic bipartite vertex-transitive graph of girth six contains cycles of lengths that are powers of two.
The study confirms the Erdős-Gyárfás conjecture for this graph class with a sharp bound of k_min ≤ 5.
Structural classification helped identify distinct families contributing to the cycle formation.
Computational verification across 1280 vertices identified precisely 14 graphs achieving the maximum symmetry.

Abstract

We prove that every cubic bipartite vertex-transitive graph of girth six contains a simplecycle whose length is a power of two, specifically one of 8, 16, or 32. This confirms theErdos-Gyárfás conjecture for this highly symmetric class with the sharp bound kmin ≤ 5.Our proof combines the structural classification of Poto£nik and Vidali, which partitionsthese graphs into four families, with a novel port voltage framework that encodes the interactionbetween ring structures and matching edges. For the toroidal family, local hexagoncombinatorics yields cycles of length 8 or 16. For the hyperbolic and dihedral truncationfamilies, we establish two independent obstructions: a local corner-cost bound arising fromantipodal port geometry that excludes 8-cycles, and a global Z2-holonomy obstruction thatexcludes 16-cycles. Despite these barriers, we prove that a canonical ground-state walk inthe quotient graph lifts to a simple 32-cycle.Computational verification over the complete census of cubic vertex-transitive graphs upto 1280 vertices confirms the theorem and identifies exactly 14 extremal graphs attainingkmin = 5.

Power-of-Two Cycles in Cubic Bipartite Vertex-Transitive Graphs of Girth Six

Key Points

Abstract

Cite This Study