To access the full text documents, please follow this link: http://hdl.handle.net/2117/11507

Vertex-transitive graphs that remain connected after failure of a vertex an its neighbors
Hamidoune, Yahya ould; Lladó Sánchez, Ana M.; López Masip, Susana Clara
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
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 $\Gamma$ be a vertex-transitive graph of degree d with order at least d+4. We give necessary and sufficient conditions for the vosperianity of $\Gamma$. Moreover, assuming that distinct vertices have distinct neighbors, we show that $\Gamma$ 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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Cayley graphs
Atom
Calculus of variations
Grafs, Teoria de
Àtoms
Càlcul de variacions
info:eu-repo/semantics/publishedVersion
Article
Wiley InterScience
         

Show full item record

Related documents

Other documents of the same author

Hamidoune, Yahya ould; Lladó Sánchez, Ana M.; López Masip, Susana Clara
Lladó Sánchez, Ana M.; López Masip, Susana Clara; Moragas Vilarnau, Jordi
Javier, Cilleruelo; Hamidoune, Yahya ould; Serra Albó, Oriol
Lladó Sánchez, Ana M.; Moragas Vilarnau, Jordi
Drmota, Michael; Lladó Sánchez, Ana M.
 

Coordination

 

Supporters