Hung's Hamiltonian decomposition conjecture for augmented cubes

An nn-dimensional augmented cube is a graph in which each vertex is represented by an nn-bit binary string, with adjacency defined according to the augmented-cube construction. A Hamiltonian decomposition is a collection of ⌊n/2⌋\lfloor n/2\rfloor pairwise edge-disjoint Hamiltonian cycles whose edges partition the edge set.

Hung's conjecture. An nn-dimensional augmented cube admits a Hamiltonian decomposition.

Hypercubes admit Hamiltonian decompositions, and the conjecture asks whether the analogous property holds for every augmented cube. As far as the source indicates, this conjecture remains open.

References

Primary source

Da-Wei Yang, Hongyang Zhang, Rong-Xia Hao and Sun-Yuan Hsieh, “A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity”, arXiv:2507.12834 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.