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.
@article{10_37236_6820,
author = {Brian G. Kodalen and William J. Martin},
title = {On the connectivity of graphs in association schemes},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {4},
doi = {10.37236/6820},
zbl = {1386.05197},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6820/}
}
TY - JOUR
AU - Brian G. Kodalen
AU - William J. Martin
TI - On the connectivity of graphs in association schemes
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/6820/
DO - 10.37236/6820
ID - 10_37236_6820
ER -
%0 Journal Article
%A Brian G. Kodalen
%A William J. Martin
%T On the connectivity of graphs in association schemes
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6820/
%R 10.37236/6820
%F 10_37236_6820
Brian G. Kodalen; William J. Martin. On the connectivity of graphs in association schemes. The electronic journal of combinatorics, Tome 24 (2017) no. 4. doi: 10.37236/6820
