Hamiltonicity of minimum distance graphs of 1-perfect codes

Alexander Mikhailovich Romanov¹

¹Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

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$.

Détail

DOI : 10.37236/2158

Classification : 05C45, 05C12, 94B25
Mots-clés : Hamiltonian cycle, minimum distance graph, Hamming code, nonlinear code, \(q\)-ary 1-perfect code