Distance regular Cayley graphs on $Z_2^n$?

Question

Let $Z_2^n$ be group $Z_2 \times Z_2 \times \cdots \times Z_2$ with operation Exclusive-or. I'd like to know if the $Cay(Z_2^n,S)$ for $S \subset Z_2^n \setminus \{0\}$ is distance regular graph or not? Or it's for some conditions? If there is a references please let me know?

Answer 1

A Cayley graph for $\mathbb{Z}^2_d$ with valency $m$ can always be constructed as a coset graph of a subgroup $C$ of $\mathbb{Z}^2_m$ - vertices are the cosets of $C$, cosets are adjacent if there is an element in one coset at Hamming distance one from an element in the second. The minimum Hamming distance between distinct elements of $C$ will be at least three.

In other words, $C$ is a linear binary code with minimum distance three. It is a theorem in Brouwer, Cohen and Neumaier "Distance-Regular Graphs" that the coset graph of $C$ is distance regular if and only $C$ is completely regular code, i.e., the distance partition of $C$ viewed as a subset of the $m$-cube is equitable. Perfect codes are distance regular, and there is a discussion of examples in BCN. (The $d$-cubes, the folded cubes, and the bilinear and alternating forms graphs over a field of even characteristic provide infinite families.)

Answer 2

Normally, the graph will not be distance-regular.

Pick your favorite (but not too small) set $S\subset\mathbb Z_2^n$. Unless you are very unlucky, there will be two elements $s_1,s_2\in S$ which are both representable as a sum of two (other) elements of $S$, but the number of representations differ: say, $$ s_1=t_1'+t_1'',\ s_2=t_2'+t_2'',\quad t_1',t_1'',t_2',t_2''\in S, $$ while $r_{2S}(s_1)\ne r_{2S}(s_2)$. Now, $t_1'$ and $t_1''$ are distance $1$ apart in the graph under consideration, and so are $t_2'$ and $t_2''$. However, the number of common neighbors of $t_1'$ and $t_1''$ is distinct from the number of common neighbors of $t_2'$ and $t_2''$ (the former is $r_{2S}(s_1)$, the latter is $r_{2S}(s_2)$).