Hamiltonicity of Minimum Distance Graphs of 1-Perfect Codes

Abstract

A 1-perfect code $\mathcal{C}_{q}^{n}$ is called Hamiltonian if its minimum distance graph $G(\mathcal{C}_{q}^{n})$ contains a Hamiltonian cycle. In this paper, for  all admissible lengths $n \geq 13$, we construct   Hamiltonian nonlinear ternary 1-perfect  codes,   and for  all admissible lengths $n \geq 21$, we construct  Hamiltonian nonlinear quaternary 1-perfect  codes. The existence of Hamiltonian nonlinear $q$-ary 1-perfect  codes of length $N = qn + 1$ is reduced to the question of the existence of such codes of length $n$. Consequently,  for   $q = p^r$, where $p$ is prime, $r \geq 1$ there exist Hamiltonian nonlinear $q$-ary 1-perfect  codes of length $n = (q ^{m} -1) / (q-1)$, $m \geq 2$. If $q =2, 3, 4$, then $ m \neq 2$.  If $q =2$, then $ m \neq 3$.