For $n$ and $m$ positive integers $n>m\ge 1$ define a graph as follows. 
The vertices are the binary strings of length $n$.
Two vertices are adjacent if they differ in exactly $m$ consecutive bits. 
The indices of the $m$ consecutive positions where $x$ and $y$ differ from each other are considered modulo $n$.
Just to clarify, if $n=6$ and $m=4$ we consider that $x=100101$ and $y=010110$ are adjacent since they differ from each other in positions 5, 6, 1 and 2.


The resulting graph has $2^n$ vertices and $n\cdot 2^{n-1}$ edges. 
Clearly, for $m=1$ one obtains the regular $n$-dimensional hypercube.
What is the number of connected components of this graph for general $m$ and $n$?


The problem arose during a discussion in the graph theory class I am teaching this semester. I believe the problem has been considered before, but I was unable to locate any reference.



The number of connected components of a generalized hypecube
Let $d$ be the GCD $(m,n)$. If $m/d$ is even, then the number of connected components is $2^d$. If $m/d$ is odd, there are $2^{d-1}$ connected components.


Consider $C$, the circulant matrix over $\mathbb{Z}/2$ whose first row is $(1,1,...,1,0,0,...,0)$. The range of $C$ is the set of points connected to $\vec 0$, so the size of the kernel counts the connected components. To have image $\vec 0$ or $\vec 1$, that is, so that for all $i$ the $i$th coordinate of the image equals the $i+1$st, a vector must satisfy only that $a\_i = a\_{i+d}$. If $m/d$ is even, all such vectors are in the kernel, and none have image $\vec{1}$. If $m/d$ is odd, then there is an additional condition that an even number of the first $d$ coordinates are $1$ so that the image is $\vec 0$ instead of $\vec 1$.


