Independence numbers of Johnson-type graphs

Abstract

We consider a family of distance graphs in ${\mathbb{R}}^n$ and find its independent numbers in some cases. Define graph $J_{\pm }(n,k,t)$ in the following way: the vertex set consists of all vectors from $\{-1,0,1{\}}^n$ with $k$ nonzero coordinates; edges connect the pairs of vertices with scalar product $t$. We find the independence number of $J_{\pm }(n,k,t)$ for $n>n_0(k,t)$ in the cases $t=0$ and $t=-1$; these cases for $k=3$ are solved completely. Also the independence number is found for negative odd $t$ and $n>n_0(k,t)$.