# The number of connected components of a generalized hypecube

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.

• This is equivalent to finding the size of the kernel of a circulant matrix over $\mathbb{Z}/2$ whose rows have $m$ consecutive $1$s. – Douglas Zare Mar 16 '14 at 14:25

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

• Thank you Douglas, that helps a lot. Just to make sure although this may very well be quite obvious: all connected components have the same cardinality, correct? – Dan Ismailescu Mar 16 '14 at 16:13
• @Dan Ismailescu: Yes, all connected components have the same cardinality. They are all translates of the range of $C$. – Douglas Zare Mar 16 '14 at 17:54