Premium
Vertex‐transitive graphs that remain connected after failure of a vertex and its neighbors
Author(s) -
Hamidoune Y. O.,
Lladó A.,
López S. C.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20521
Subject(s) - combinatorics , mathematics , vertex (graph theory) , aperiodic graph , graph , vertex transitive graph , symmetric graph , discrete mathematics , cayley graph , transitive relation , graph power , line graph , voltage graph
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