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

Hamidoune, Yahya Ould; Lladó, A.; López Masip, Susana-Clara

doi:https://doi.org/10.1002/jgt.20521

View/Open

Postprint (284.0Kb)

Issue date

2011

Author

Hamidoune, Yahya Ould

Lladó, A.

López Masip, Susana-Clara

Suggested citation

Hamidoune, Yahya Ould; Lladó, A.; López Masip, Susana-Clara; . (2011) . Vertex‐transitive graphs that remain connected after failure of a vertex and its neighbors. Journal of Graph Theory, 2011, vol. 67, num. 2, p. 124-138. https://doi.org/10.1002/jgt.20521.

Abstract

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.

URI

http://hdl.handle.net/10459.1/66511

DOI

https://doi.org/10.1002/jgt.20521

Is part of

Journal of Graph Theory, 2011, vol. 67, num. 2, p. 124-138