On the connectivity of graphs in association schemes (Q1691090)

Summary: Let \((X,\mathcal{R})\) be a commutative association scheme and let \(\Gamma=(X,R\cup R^\top)\) be a connected undirected~ graph where \(R\in \mathcal{R}\). Godsil (resp., Brouwer) conjectured that the edge connectivity (resp., vertex connectivity) of \(\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 \(\Gamma\) if they have identical neighborhoods: \(\Gamma(a)=\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 \(\Gamma\) results in a connected graph. Using this and other tools, we find lower bounds on the connectivity of \(\Gamma\), especially in the case where \(\Gamma\) has diameter two. Among the applications of these results, we prove that the only connected relations in symmetric association schemes which admit a disconnecting set of size two are those which are ordinary polygons.