On Kotzig's Perfect Set Problem of Hamiltonian Cycle Decompositions of the Complete Graph

ABSTRACT A Hamiltonian cycle decomposition (HCD) of is a set of Hamiltonian cycles in which each 1‐path of appears exactly once. A Dudeney set of is a set of Hamiltonian cycles in which each 2‐path of appears exactly once. Kotzig's perfect set of HCDs of is a set of HCDs whose union forms a Dudeney set. A set of ‐pairwise compatible HCDs (‐PCH) of is a set of HCDs such that each 2‐path of appears at most once. This paper proposes an orderly algorithm for finding a ‐PCH and shows that no 7‐PCH (i.e., no perfect set of HCDs) exists for . It also proposes an orderly algorithm for finding a perfect set whose automorphism group is or , and shows the existence of a perfect set of HCDs of and . These are the first instances of perfect sets of HCDs in complete graphs to be found since Kotzig posed the problem in 1979.