Hung's Hamiltonian decomposition conjecture for augmented cubes
Hung's Hamiltonian decomposition conjecture for augmented cubes
An -dimensional augmented cube is a graph in which each vertex is represented by an -bit binary string, with adjacency defined according to the augmented-cube construction. A Hamiltonian decomposition is a collection of pairwise edge-disjoint Hamiltonian cycles whose edges partition the edge set.
Hung's conjecture. An -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.