Cospectral mates for the union of some classes in the Johnson association scheme

Abstract

Let $n\ge k\ge 2$ be two integers and $S$ a subset of $\{0,1,\dots ,k-1\}$. The graph $J_S(n,k)$ has as vertices the $k$-subsets of the $n$-set $[n]=\{1,\dots ,n\}$ and two $k$-subsets $A$ and $B$ are adjacent if $|A\cap B|\in S$. In this paper, we use Godsil-McKay switching to prove that for $m\ge 0$, $k\ge \max (m+2,3)$ and $S=\{0,1,...,m\}$, the graphs $J_S(3k-2m-1,k)$ are not determined by spectrum and for $m\ge 2$, $n\ge 4m+2$ and $S=\{0,1,...,m\}$ the graphs $J_S(n,2m+1)$ are not determined by spectrum. We also report some computational searches for Godsil-McKay switching sets in the union of classes in the Johnson scheme for $k\le 5$.

9 pages, no figures, 3 tables; 2nd version contains improved results compared to the 1st version