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 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Designs, online erschienen am 08.05.2026. Verfasst von Nobuaki Mutoh. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
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