|
Notes:
|
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, |(H ∪ Ha)(S ∪ {1})| ≥ min(|G| − 1, |H ∪ Ha| + |S| + 1). If moreover S is aperiodic, then Cay(G, S) is vosperian if and only if it is superconnected.
Research supported by the Ministry of Science and Innovation, Spain
under project MTM2008-06620-C03-01/MTM. Research done when the last author was visiting
Universit´e Pierre et Marie Curie, E. Combinatoire, Paris, supported by the Ministry of Science
and Innovation, Spain under the National Mobility Programme of Human Resources, Spanish
National Programme I-D-I 2008–2011. |
