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, SusanaClara;
.
(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. 124138.
https://doi.org/10.1002/jgt.20521.
Metadata
Show full item recordAbstract
A dregular 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 vertextransitive 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. 124138European 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, SusanaClara; Muntaner Batle, F. A. (Springer, 2015)FigueroaCenteno 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 VertexTransitive Digraphs
Hamidoune, Yahya Ould; Lladó, A.; López Masip, SusanaClara (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, SusanaClara; Moragas, J. (Elsevier, 2010)Let T be a tree with m edges. A wellknown 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 ...