Decomposing complete graphs into squares of Hamilton cycles
For $n \ge 5$ let $C_n^2$, the square of the $n$-cycle, be the graph on $\mathbb Z/n\mathbb Z$ joining every pair of vertices at cyclic distance one or two. It is $4$-regular, so a partition of the edges of the complete graph $K_n$ into copies of $C_n^2$ requires $n \equiv 1 \pmod 4$, and then consists of $(n-1)/4$ edge-disjoint spanning copies. No such partition exists for $n = 9$. Parczyk, Rathke and Szabó constructed one for every prime $p \equiv 1 \pmod 4$ such that the multiplicative order of $2$ modulo $p$ is divisible by four, in particular for every prime $p \equiv 5 \pmod 8$. Ferber, Lee and Mousset showed that edge-disjoint copies of $C_n^2$ can cover all but $o(n^2)$ edges of $K_n$. For large $n$ the statement below is a special case of a conjecture of Glock, Joos, Kim, Kühn and Osthus: if $F_1, \dots, F_t$ are $n$-vertex graphs, each regular of degree at most a fixed $\Delta$, with degrees summing to $n - 1$, then, for every $n$ large enough in terms of $\Delta$, $K_n$ decomposes into $F_1, \dots, F_t$.
Problem. Is it true that, whenever $n \ge 5$, $n \equiv 1 \pmod 4$ and $n \ne 9$, the edges of $K_n$ can be partitioned into copies of $C_n^2$?
Source: Parczyk, Rathke and Szabó (2026), Conjecture 4.1, after their Question 1.2; for large n it is a special case of Glock, Joos, Kim, Kühn and Osthus (2021), Conjecture 1.4.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, combinatorial designs, graph decompositions, Hamilton cycles
References
@article{parczyk2026,
author = {Parczyk, Olaf and Rathke, Silas and Szab{\'o}, Tibor},
title = {The maximum diameter of 2-dimensional simplicial complexes},
journal = {Discrete Comput. Geom.},
volume = {76},
number = {3},
year = {2026},
pages = {1687--1724},
doi = {10.1007/s00454-026-00844-8},
eprint = {2511.10144},
archivePrefix = {arXiv},
}
@article{glock2021,
author = {Glock, Stefan and Joos, Felix and Kim, Jaehoon and K{\"u}hn, Daniela and Osthus, Deryk},
title = {Resolution of the {O}berwolfach problem},
journal = {J. Eur. Math. Soc. (JEMS)},
volume = {23},
number = {8},
year = {2021},
pages = {2511--2547},
doi = {10.4171/JEMS/1060},
eprint = {1806.04644},
archivePrefix = {arXiv},
}
@article{ferber2017,
author = {Ferber, Asaf and Lee, Choongbum and Mousset, Frank},
title = {Packing spanning graphs from separable families},
journal = {Israel J. Math.},
volume = {219},
number = {2},
year = {2017},
pages = {959--982},
doi = {10.1007/s11856-017-1504-0},
}
@misc{aim-hamilton-square-decomposition,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Decomposing complete graphs into squares of Hamilton cycles}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/612-hamilton-square-decomposition.md},
note = {Entry 612 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00351, "Decomposing complete graphs into squares of Hamilton cycles", clopen.solutions.