Universitat de Lleida
    • English
    • català
    • español
  • English 
    • English
    • català
    • español
  • Login
Repositori Obert UdL
View Item 
  •   Home
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • View Item
  •   Home
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

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

Thumbnail
View/Open
Postprint (284.0Kb)
Issue date
2011
Author
Hamidoune, Yahya Ould
Lladó, A.
López Masip, Susana-Clara
Suggested 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.
Impact


Web of Science logo    citations in Web of Science

Scopus logo    citations in Scopus

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
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.
URI
http://hdl.handle.net/10459.1/66511
DOI
https://doi.org/10.1002/jgt.20521
Is part of
Journal of Graph Theory, 2011, vol. 67, num. 2, p. 124-138
European research projects
Collections
  • Publicacions de projectes de recerca del Plan Nacional [2215]
  • Articles publicats (Matemàtica) [266]

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 ...

Contact Us | Send Feedback | Legal Notice
© 2021 BiD. Universitat de Lleida
Metadata subjected to 
 

 

Browse

All of the repositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

Statistics

View Usage Statistics

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contact Us | Send Feedback | Legal Notice
© 2021 BiD. Universitat de Lleida
Metadata subjected to