Hamilton cycles in $\{0,1\}^n$ with fixed Hamming distance

Question

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.

Answer 1

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

Answer 2

Here is a different perspective on the problem (which also settles the case left open by Max Alekseyev's answer).

$H(n,k)$ is a Cayley graph of the group $G = \{0,1\}^n$ with respect to the set $M_k$ of elements with exactly $k$ non-zero entries. It is well known (and easy to prove by induction on the number of generators) that any connected Cayley graph of an abelian group contains a Hamilton cycle. So we only need to check when $H(n,k)$ is connected, or equivalently, if $M_k$ is a generating set of $G$.

Note that any element of $M_2$ is the sum of two elements in $M_k$, hence $M_{k-2}$ is contained in the subgroup generated by $M_k$. If $k$ is odd, then this implies that $M_k$ generates $M_1$ and thus all of $G$. If $k$ is even, then (as noted by Max Alekseyev) $M_k$ generates the same subgroup of index $2$ as $M_2$.