Improved cubic graph constructions avoiding power-of-two cycle lengths

We investigate explicit cubic graph constructions avoiding cycles of power-of-two lengths, motivated by the Erdős–Gyárfás conjecture. Let f(k) denote the minimum number of vertices in a finite simple cubic graph containing no cycles of lengths 4, 8, ..., 2^k. We construct an explicit connected cubic graph on 370 vertices and 555 edges containing no cycles of lengths 4, 8, 16, or 32. This establishes f(5) ≤ 370, improving the previously reported 450-vertex construction. We also develop a functional-orientation method using three-terminal graph gadgets. Writing n₃(g) for the minimum order of a connected cubic graph of girth at least g, we prove the general upper bound f(k) ≤ 15n₃(2^(k−2)), for k ≥ 4. A refinement replacing one 15-vertex gadget with a seven-vertex gadget further establishes f(k) ≤ 15n₃(2^(k−2)) − 8, for k ≥ 5. Combining the refined theorem with a reported 702-vertex cubic graph of girth 16 gives f(6) ≤ 10,522, compared with the previously reported upper bound of 32,640. The numerical consequence based on the 702-vertex graph relies on an external existence record; that graph was not independently reconstructed in this work. The supplementary materials include the complete 370-vertex graph in graph6 format, its edge list, Python and C++ verification programs, cycle-enumeration results, checksums, and an explicit 64-cycle witness. These materials support independent reproduction of the finite construction. The results establish improved quantitative bounds and constructive methods. They do not resolve the original Erdős–Gyárfás conjecture. The manuscript is a research preprint and has not undergone external peer review; broader scientific priority remains subject to independent assessment.