On Kotzig's Perfect Set Problem of Hamiltonian Cycle Decompositions of the Complete Graph
Journal of Combinatorial Designs · 2026-08 · 34 (8) · 388-409
DOI: 10.1002/jcd.70017 ↗At a glance
Journal article in Journal of Combinatorial Designs, published online on 2026-05-08. Written by Nobuaki Mutoh. 30 references. The full text is freely available (open access, CC BY 4.0).
Abstract (original language)
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.
Cite
APA
Mutoh, N. (2026). On Kotzig's Perfect Set Problem of Hamiltonian Cycle Decompositions of the Complete Graph. Journal of Combinatorial Designs, 34(8), 388-409. https://doi.org/10.1002/jcd.70017
Vancouver
Mutoh N. On Kotzig's Perfect Set Problem of Hamiltonian Cycle Decompositions of the Complete Graph. Journal of Combinatorial Designs. 2026;34(8):388-409. doi:10.1002/jcd.70017
BibTeX
@article{Mutoh2026,
author = {Mutoh, Nobuaki},
title = {On Kotzig's Perfect Set Problem of Hamiltonian Cycle Decompositions of the Complete Graph},
journal = {Journal of Combinatorial Designs},
year = {2026},
volume = {34},
number = {8},
pages = {388--409},
doi = {10.1002/jcd.70017}
}
EUVIMED