On Isoperimetric Connectivity in Vertex-Transitive Graphs
Yahya Ould Hamidoune, Anna Lladó, Oriol Serra, Ralph Tindell · SIAM Journal on Discrete Mathematics · 2000
We shall define the k-isoperimetric connectivity $\lambda _k$ of a regular graph $\Gamma $ as the minimum number of arcs originating in a set with cardinality not exceeding half the order of the graph and containing at least k vertices. Clearly $\lambda _k \leq dk-e_k$, where d is the degree of $\Gamma$ and $e_k$ is the maximal number of edges induced on a set of k vertices. We shall show that Cayley graphs with a prime order and arc-transitive graphs have $\lambda _k =dk-e_k$, provided that $d\geq 3k-3$. We describe all vertex-transitive graphs where $\lambda _2\leq 2d-3$.