Vertex‐transitive graphs that remain connected after failure of a vertex and its neighbors

A d ‐regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex and its neighbors will be called vosperian . Let Γ be a vertex‐transitive graph of degree d with order at least d +4. We give necessary and sufficient conditions for the vosperianity of Γ. Moreover, assuming that distinct vertices have distinct neighbors, we show that Γ is vosperian if and only if it is superconnected. Let G be a group and let S ⊂ G \{1} with S = S −1 . We show that the Cayley graph, Cay ( G, S ), defined on G by S is vosperian if and only if G \( S ∪{1}) is not a progression and for every non‐trivial subgroup H and every a ∈ G ,If moreover S is aperiodic, then Cay ( G, S ) is vosperian if and only if it is superconnected. © 2011 Wiley Periodicals, Inc. J Graph Theory 67:124‐138, 2011