Show simple item record

dc.contributor.authorHamidoune, Yahya Ould
dc.contributor.authorLladó, A.
dc.contributor.authorLópez Masip, Susana-Clara
dc.date.accessioned2019-07-02T10:59:05Z
dc.date.available2019-07-02T10:59:05Z
dc.date.issued2011
dc.identifier.issn0364-9024
dc.identifier.urihttp://hdl.handle.net/10459.1/66511
dc.description.abstractA 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.
dc.description.sponsorshipResearch supported by the Ministry of Science and Innovation, Spain under project MTM2008-06620-C03-01/MTM. Research done when the last author was visiting Universit´e Pierre et Marie Curie, E. Combinatoire, Paris, supported by the Ministry of Science and Innovation, Spain under the National Mobility Programme of Human Resources, Spanish National Programme I-D-I 2008–2011.
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.publisherWiley
dc.relationMICINN/PN2008-2011/MTM2008-06620-C03-01/MTM
dc.relation.isformatofVersió postprint del document publicat a: https://doi.org/10.1002/jgt.20521
dc.relation.ispartofJournal of Graph Theory, 2011, vol. 67, num. 2, p. 124-138
dc.rights(c) Wiley, 2011
dc.titleVertex‐transitive graphs that remain connected after failure of a vertex and its neighbors
dc.typeinfo:eu-repo/semantics/article
dc.date.updated2019-07-02T10:59:05Z
dc.identifier.idgrec028472
dc.type.versioninfo:eu-repo/semantics/acceptedVersion
dc.rights.accessRightsinfo:eu-repo/semantics/openAccess
dc.identifier.doihttps://doi.org/10.1002/jgt.20521


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record