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

View/ Open
Issue date
2011Suggested 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.
Metadata
Show full item recordAbstract
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.
Is part of
Journal of Graph Theory, 2011, vol. 67, num. 2, p. 124-138European research projects
Collections
Related items
Showing items related by title, author, creator and subject.
-
Connectivity and other invariants of generalized products of graphs
López Masip, Susana-Clara; Muntaner Batle, F. A. (Springer, 2015)Figueroa-Centeno et al. [4] introduced the following product of digraphs let D be a digraph and let Γ be a family of digraphs such that V (F) = V for every F∈Γ . Consider any function h:E(D)→Γ . Then the product D⊗hΓ is ... -
On Vosperian and Superconnected Vertex-Transitive Digraphs
Hamidoune, Yahya Ould; Lladó, A.; López Masip, Susana-Clara (Springer, 2013)We investigate the structure of a digraph having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization ... -
Every tree is a large subtree of a tree that decomposes Kn or Kn,n
Lladó, A.; López Masip, Susana-Clara; Moragas, J. (Elsevier, 2010)Let T be a tree with m edges. A well-known conjecture of Ringel states that every tree T with m edges decomposes the complete graph K2m+1. Graham and H¨aggkvist conjectured that T also decomposes the complete bipartite ...