×

Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors. (English) Zbl 1217.05121

Summary: 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 \subset G \setminus \{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 \setminus (S \cup \{1\})\) is not a progression and for every non-trivial subgroup \(H\) and every \(a \in G\),
\[ \left|(H \cup Ha)(S \cup \{1\})\right| \min (|G| -1, |H \cup Ha| + |S| + q). \] If moreover \(S\) is aperiodic, then \(Cay(G, S)\) is vosperian if and only if it is superconnected.

MSC:

05C40 Connectivity
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

References:

[1] Balbuena, Extraconnectivity of s-geodetic digraphs and graphs, Discrete Math 195 (1-3) pp 39– (1999) · Zbl 0927.05049 · doi:10.1016/S0012-365X(98)00163-0
[2] Balbuena, On the connectivity and superconnectivity of bipartite digraphs and graphs, Ars Combin 61 pp 3– (2001) · Zbl 1071.05544
[3] Balbuena, On the order and size of s-geodetic digraphs with given connectivity, Discrete Math 174 (1-3) pp 19– (1997) · Zbl 0886.05086 · doi:10.1016/S0012-365X(96)00314-7
[4] Balbuena, Extraconnectivity of graphs with large minimum degree and girth, Discrete Math 167/168 pp 85– (1997) · Zbl 0874.05033 · doi:10.1016/S0012-365X(96)00218-X
[5] Balbuena, Superconnectivity of bipartite digraphs and graphs, Discrete Math 197/198 pp 61– (1999) · Zbl 0933.05089 · doi:10.1016/S0012-365X(99)90041-9
[6] Balbuena, Diameter-girth sufficient conditions for optimal extraconnectivity in graphs, Discrete Math 308 (16) pp 3526– (2008) · Zbl 1172.05035 · doi:10.1016/j.disc.2007.07.012
[7] Balbuena, On the connectivity and superconnected graphs with small diameter, Discrete Appl Math 58 (5) pp 397– (2010) · Zbl 1225.05153 · doi:10.1016/j.dam.2009.10.002
[8] Boesch, Synthesis of reliable networks. A survey, IEEE Trans Reliab 35 pp 240– (1986) · Zbl 0603.90060 · doi:10.1109/TR.1986.4335424
[9] Boesch, Circulants and their connectivities, J Graph Theory 8 (4) pp 487– (1984) · Zbl 0549.05048 · doi:10.1002/jgt.3190080406
[10] Bondy, Graduate Texts in Mathematics 244, in: Graph Theory (2008) · doi:10.1007/978-1-84628-970-5
[11] Bollobàs, Graduate Texts in Mathematics 184, in: Modern Graph Theory (1998) · doi:10.1007/978-1-4612-0619-4
[12] Fàbrega, Extraconnectivity of graphs with large girth, Discrete Math 127 pp 163– (1994) · Zbl 0797.05058 · doi:10.1016/0012-365X(92)00475-7
[13] Fàbrega, On the extraconnectivity of graphs, Discrete Math 155 (1-3) pp 49– (1996) · Zbl 0857.05064 · doi:10.1016/0012-365X(94)00369-T
[14] Fiol, Connectivity and superconnectivity of large graphs and digraphs, Ars Combin 29 (B) pp 5– (1990) · Zbl 0708.05034
[15] Fiol, The superconnectivity of large digraphs and graphs, Discrete Math 124 (1-3) pp 67– (1994) · Zbl 0791.05068 · doi:10.1016/0012-365X(92)00051-R
[16] Fiol, Short paths and connectivity in graphs and digraphs, Ars Combin 29 (B) pp 17– (1990) · Zbl 0708.05025
[17] Hamidoune, Sur les atomes d’un graphe orienté, C R Acad Sci Paris A 284 pp 1253– (1977)
[18] Hamidoune, On the connectivity of Cayley digraphs, Europ J Combin 5 pp 309– (1984) · Zbl 0561.05028 · doi:10.1016/S0195-6698(84)80034-7
[19] Hamidoune, An isoperimetric method in additive theory, J Algebra 179 (2) pp 622– (1996) · Zbl 0842.20029 · doi:10.1006/jabr.1996.0028
[20] Hamidoune, Subsets with small sums in Abelian groups I: The Vosper property, Europ J Combin 18 (5) pp 541– (1997) · Zbl 0883.05065 · doi:10.1006/eujc.1995.0113
[21] Hamidoune, Some results in additive number theory I: The critical pair Theory, Acta Arith 96 (2) pp 97– (2000) · Zbl 0985.11011 · doi:10.4064/aa96-2-1
[22] Y. O. Hamidoune Hyper-atoms and the Kemperman’s critical pair theory
[23] Hamidoune, Some additive applications of the isoperimetric approach, Annals Insitute Fourier, Grenoble 58 (6) pp 2007– (2008) · Zbl 1173.05019 · doi:10.5802/aif.2404
[24] Hamidoune, Vosperian and superconnected Abelian Cayley digraphs, Graphs Combin 7 pp 143– (1991) · Zbl 0736.05047 · doi:10.1007/BF01788139
[25] Hamidoune, On isoperimetric connectivity in vertex-transitive graphs, SIAM J Discrete Math 13 (1) pp 139– (2000) · Zbl 0951.05051 · doi:10.1137/S089548019630635X
[26] van den Heuvel, On the edge connectivity, hamiltonicity and toughness of vertex-transitive graphs, J Comb Theory Ser B 77 (1) pp 138– (1999) · Zbl 1024.05054 · doi:10.1006/jctb.1999.1917
[27] Liang, Super-connectivity and hyperconnectivity of vertex-transitive bipartite graphs, Graphs Combin 23 (3) pp 309– (2007) · Zbl 1122.05052 · doi:10.1007/s00373-007-0725-0
[28] Mader, Über den Zusammenhang symmetricher Graphen, Arch Math 21 pp 331– (1970) · Zbl 0201.56804 · doi:10.1007/BF01220924
[29] Mader, Eine Eigenschaft der Atome endlicher Graphen, Arch Math 22 pp 333– (1971) · Zbl 0214.51503 · doi:10.1007/BF01222585
[30] Marcote, Diameter, short paths and superconnectivity in digraphs, Discrete Math 288 (1-3) pp 113– (2004) · Zbl 1062.05085 · doi:10.1016/j.disc.2004.06.011
[31] Meng, Connectivity of vertex and edge transitive graphs, Discrete Appl Math 127 pp 601– (2003) · Zbl 1018.05057 · doi:10.1016/S0166-218X(02)00391-8
[32] Meng, Super-connected arc-transitive digraphs, Discrete Appl Math 157 pp 653– (2009) · Zbl 1173.05326 · doi:10.1016/j.dam.2008.08.018
[33] Sabidussi, Vertex-transitive graphs, Monash Math 68 pp 426– (1964) · Zbl 0136.44608 · doi:10.1007/BF01304186
[34] Serra, London Mathematical Society Lecture Note Series 327, in: Surveys in Combinatorics pp 119– (2005) · doi:10.1017/CBO9780511734885.007
[35] Watkins, Connectivity of transitive graphs, J Combin Theory 8 pp 23– (1970) · Zbl 0185.51702 · doi:10.1016/S0021-9800(70)80005-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.