ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.