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.

Sources & referencesView supporting material

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.