Hamilton Cycles – Hamilton Cycles in $\{0,1\}^n$ with Fixed Hamming Distance

computer sciencegraph theoryhamiltonian-paths

Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge set $$E(n,k) = \{(a, b)\in (\{0,1\}^n)^2 : d_h(a, b) = k\}.$$

Question. For what values of $k\in \{2,\ldots n-1\}$ does $H(n,k)$ have a Hamilton cycle?

Note 1. Hamilton cycles in $H(n,1)$ are called Gray codes.

Note 2. A necessary (but maybe not sufficient) condition for $H(n,k)$ to have a Hamilton cycle is that $\text{gcd}(k,2^n) = 1$, otherwise $H(n,k)$ is not a connected graph.

Best Answer

I believe these are exactly odd $k$.

Indeed, it can be easily seen that if $k$ is even, then a cycle starting at $0^n$ can visit only those vectors that have even number of $1$'s, and so it cannot be Hamiltonian.

On the other hand, there exist long-run Gray codes where any consecutive $\leq n-3\log_2 n$ bit changes happening at distinct positions. So, for odd $k\leq n-3\log_2 n$ traversing such a code with step $k$ produces a Hamiltonian cycle in $H(n,k)$.

Also, for an even $n$, inverting every second element of a cycle in $H(n,k)$ produces a cycle in $H(n,n-k)$.

It remains to address the case of odd $n$ and odd $k>n-3\log_2 n$.

Related Question