On the connectivity of graphs in association schemes

Let $(X,\mathcal{R})$ be a commutative association scheme and let $\mathrm{\Gamma }=(X,R\cup R^{\mathrm{\top }})$ be a connected undirected graph where $R\in $\mathcal{R}$$. Godsil (resp., Brouwer) conjectured that the edge connectivity (resp., vertex connectivity) of $\mathrm{\Gamma }$ is equal to its valency. In this paper, we prove that the deletion of the neighborhood of any vertex leaves behind at most one non-singleton component. Two vertices $a,b\in X$ are called “twins” in $\mathrm{\Gamma }$ if they have identical neighborhoods: $\mathrm{\Gamma }(a)=\mathrm{\Gamma }(b)$. We characterize twins in polynomial association schemes and show that, in the absence of twins, the deletion of any vertex and its neighbors in $\mathrm{\Gamma }$ results in a connected graph. Using this and other tools, we find lower bounds on the connectivity of $\mathrm{\Gamma }$, especially in the case where $\mathrm{\Gamma }$ has diameter two. Among the applications of these results, we find that the only connected relations in symmetric association schemes which admit a disconnecting set of size two are those which are ordinary polygons.