Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d\_h(a, b)$ denote the [Hamming distance](https://en.wikipedia.org/wiki/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.



Hamilton cycles in $\{0,1\}^n$ with fixed Hamming distance
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](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v10i1r27) 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$.


